题意:求出度为0的强连通分支。
分析:采用邻接阵的强连通分支tarjan模板。
View Code
const int maxn = 5005, maxm = 100005; struct Edge { int v, next; }edge[maxm]; int n, m, ncount, idx; int head[maxn]; int dfn[maxn], low[maxn]; bool vis[maxn], instk[maxn]; int stk[maxn], top, cpn_num, cpn[maxn]; int out[maxn]; void addedge(int a, int b) { //printf("%d %d\n", a, b); edge[ncount].v = b; edge[ncount].next = head[a]; head[a] = ncount++; } void tarjan(int u) { vis[u] = true; stk[top++] = u; instk[u] = true; dfn[u] = low[u] = idx++; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; if (!vis[v]) { tarjan(v); low[u] = min(low[u], low[v]); }else if (instk[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] != low[u]) return; int v; do { v = stk[--top]; instk[v] = false; cpn[v] = cpn_num; }while(u != v); cpn_num++; } CALL: memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); memset(instk, 0, sizeof(instk)); memset(out, 0, sizeof(out)); input(); idx = 0; top = 0; cpn_num = 0; for (int i = 0; i < n; i++) if (!vis[i]) tarjan(i);