Tarjan算法 消息的传递
安昙
2018-07-17 08:54:14
# 描述：
我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有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.in:
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.out:
2
------------
用Trajan求强连通分量，缩点，其实并不需要重新构图，只需要把每个强连通的入度统计出来，答案就是入度为0的个数;
接下来上题解：
```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]]++;/*两个不同联通图之间有一条单向边*/
/*存在边j-->i，j,i属于两个不同的联通图，所以i所属的联通图的入度++*/
for(int i=1;i<=num;i++)if(rd[i]==0)ans++;
/*只需把消息传给入度为零的联通图(因为没有别的联通图可以传到它)*/
/*其它的联通图，只有中间有边就能互相传递*/
/*所以我们只需要统计入度为0的联通图*/
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();
}
```