1.拓扑排序
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <set> #include <vector> using namespace std; #define maxn 105 typedef long long ll; vector<int> G[maxn]; struct node{ int time; int id; bool operator < (const node & rhs)const{ return time > rhs.time; } }nodes[maxn]; int n; bool vis[maxn]; int nowTime = 0; void dfs(int u){ nowTime ++; vis[u] = true; for(int i = 0;i < G[u].size();i ++){ int v = G[u][i]; if(!vis[v]) dfs(v); } nowTime ++;s nodes[u].time = nowTime; } void top(void){ for(int i = 1;i <= n;i ++){ if(!vis[i]){ dfs(i); } } } int main(void){ cin >> n; memset(vis,false,sizeof(vis)); for(int i = 1;i <= n;i ++){ int b; nodes[i].id = i; while(cin >> b && b != 0){ G[i].push_back(b); } } nowTime = 0; top(); sort(nodes+1,nodes+n+1); for(int i = 1;i <= n;i ++){ cout << nodes[i].id << " "; //按拓扑排序输出节点 } cout << endl; return 0; }
2.无向图割点
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #define maxn 100005 using namespace std; vector<int> G[maxn]; int dfn[maxn],vis[maxn],low[maxn]; bool isGedian[maxn]; //标记该点是否是割点 int fa[maxn]; //父亲节点 int depth; int root; int ans; void init(){ memset(isGedian,0,sizeof(isGedian)); memset(fa,0,sizeof(fa)); memset(vis,0,sizeof(vis)); for(int i = 0;i < maxn;i ++){ G[i].clear(); } } void dfs(int cur,int depth){ int cnt = 0; //记录当前节点的孩子个数 low[cur] = dfn[cur] = depth; vis[cur] = true; for(int i = 0;i < G[cur].size();i ++){ int v = G[cur][i]; if(!vis[v] && v != fa[cur]){ fa[v] = cur; dfs(v,depth+1); cnt ++; low[cur] = min(low[cur],low[v]); if(low[v] >= dfn[cur] && root!= cur){ if(!isGedian[cur]){ ans ++; } isGedian[cur] = true; } } else{ low[cur] = min(low[cur],dfn[v]); } } if(root == cur && cnt > 1){ if(!isGedian[cur]){ ans ++; } isGedian[cur] = true; } } int main() { int n,a,b; while(cin >> n && n){ ans = 0; init(); while(cin >> a && a){ while(getchar() != ' ') { cin >> b; G[a].push_back(b); G[b].push_back(a); } } root = 1; dfs(1,0); cout << ans << endl; } return 0; }
3.强连通分量
#include <iostream> #include <algorithm> #include <cstring> #include <vector> #define maxn 10005 using namespace std; vector<int> G[maxn],Gt[maxn]; //Gt存放补图 vector<int> S; int vis[maxn]; int sccno[maxn]; //每个节点所在强连通分量的序号 int scc_cnt; //强连通分量个数 int outdegree[maxn]; //连通分量的出度 void dfs1(int u){ //目的，按每个节点结束搜索的时间排序 if(vis[u]) return; vis[u] = 1; for(int i = 0;i < G[u].size();i ++){ int v = G[u][i]; dfs1(v); } S.push_back(u); } void dfs2(int u){ if(sccno[u]) return; sccno[u] = scc_cnt; for(int i = 0;i < Gt[u].size();i ++){ int v = Gt[u][i]; dfs2(v); } } void find_scc(int n){ S.clear(); scc_cnt = 0; memset(sccno,0,sizeof(sccno)); memset(vis,0,sizeof(vis)); memset(outdegree,0,sizeof(outdegree)); for(int i = 1;i <= n;i ++){ dfs1(i); } for(int i = n-1;i >= 0 ;i --){ if(!sccno[S[i]]){ scc_cnt ++; dfs2(S[i]); } } }
4.单源最短路径Dijkstra
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #define maxn 105 #define INF 1e9+9 using namespace std; int d[maxn]; //s到各个边的距离 int head[maxn]; bool done[maxn]; //是否已完全标号 int edgesCnt; //边的数量 int n; struct Edge{ int to; //边的终点 int dist; //边的长度 int next; //下一条边的编号 }edges[maxn*maxn]; struct HeapNode{ int u; //节点编号 int d; //节点到源节点的距离 bool operator < (const HeapNode& rhs) const{ return d > rhs.d; } }; void init(){ edgesCnt = 0; memset(head,-1,sizeof(head)); } void addEdge(int from,int to,int dist){ edges[edgesCnt] = {to,dist,head[from]}; head[from] = edgesCnt; edgesCnt ++; } void Dijkstra(int s){ priority_queue<HeapNode> Q; for(int i = 0;i <= n;i ++) d[i] = INF; memset(done,false,sizeof(done)); d[s] = 0; Q.push((HeapNode){s,0}); while(!Q.empty()){ HeapNode x = Q.top(); Q.pop(); int u = x.u; if(done[u]) continue; done[u] = true; for(int i = head[u];i != -1;i = edges[i].next){ Edge e = edges[i]; int v = e.to; if(d[v] > d[u] + e.dist){ d[v] = d[u] + e.dist; Q.push((HeapNode){v,d[v]}); } } } }