Tarjan算法缩点

在一些点的集合里，这些点**两两之间可以互相到达**，他们被称为**强连通分量**，因为这个集合十分特别（每一个点都有相同的性质），我们可以把他们看作一个点，因为假如有一条边连接到这个集合，就可以从另外一条连着这个集合的**任意**一个点的边出去，而**缩点**就要运用到tarjan tarjan的代码实现网上到处都是 算法核心 ```cpp stack<int> s; tarjan(int v0) { low[v0]=dfn[v0]=++sign; s.push(v0); for(register int i=1;i;i=a[i].next) { int to=a[i].to; if(dfn[v0]==0) { tarjan(to) low[v0]=min(low[v0],low[to]) } else if(vis[to]) { low[v0]=min(low[v0],dfn[v0]); } } if(low[i]==dfn[i]) { num++; do { int now=s.top(); s.pop(); belong[now]=num; } while(t!=i); } } ``` 以这道题为例 ------------ 【图的连通性】消息的传递 Description 　　我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（<=1000）个袁绍的奸细，将他们从1到N进行编号，同时他们之间存在一种传递关系，即若C[i，j]=1，则奸细i能将消息直接传递给奸细j。 　　现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细 Input 　　文件的第一行为N，第二行至第N+1行为N*N的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能将消息直接传递给奸细J）。 Output 　　输出文件只有一行：即我们的郭嘉大大首先至少要传递的奸细个数 。 Sample Input ``` 8 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 ``` Sample Output ``` 2 ``` ------------ ``` belong[i]指i属于第几个强联通分量 rd[i]指第i个节点的入度 low[i]表示节点i在栈中能找到的最早祖先的标号 dfn[i]节点i的时间戳 vis[i]节点i是否在栈中 ``` ------------ ```cpp #include<cstdio> #include<iostream> using namespace std; int n,d[1005][1005];/*d[i][j]表示i与j之间是否有一条边*/ int dfn[1005];/*dfn[i]表示递归访问i节点的顺序（编号）*/ int low[1005];/*low[i]表示i在栈中能找到的最早祖先的标号*/ int vis[10005];/*vis[i]表示i节点是否在栈中*/ int belong[10005];/*belong[i]表示i节点属于第几个联通图*/ int rd[10005];/*rd[i]表示第i个联通图的入度*/ int q[1005]; /*栈*/ int num;/*联通图的数量*/ int sign;/*给节点顺序先后的标号增量*/ int top=0;/*栈顶*/ void tarjan(int i) { sign++; dfn[i]=low[i]=sign;/*初始化，把i的祖先设为自己*/ q[++top]=i;/*把i入栈，之后的装i的子树*/ vis[i]=1;/*i在栈中*/ for(int j=1;j<=n;j++) { if(d[i][j])/*i和j之间有路*/ { if(dfn[j]==0)/*没访问过j节点*/ { tarjan(j); low[i]=min(low[i],low[j]);/*更新i的最早祖先*/ } else if(vis[j])/*j已经在栈中，说明边ij是一条返祖边*/ low[i]=min(low[i],dfn[j]);/*dfn[j]是否是i节点的更早祖先的编号*/ } } int t; if(low[i]==dfn[i])/*i是一个强联通分量*/ { num++;/*总联通图数量++，这个联通图的编号是num*/ do { t=q[top--]; vis[t]=0;/*弹栈*/ belong[t]=num;/*设置当前t节点属于这个联通图*/ } while(t!=i);/*清扫这个强联通图，t到i之间的所有强联通分量都属于这一个联通图*/ } } void deal() { int ans=0; for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[j][i]&&belong[i]!=belong[j])rd[belong[i]]++;//统计每一个点集的入读 for(int i=1;i<=num;i++)if(rd[i]==0)ans++; printf("%d",ans); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&d[i][j]); deal(); } ```