什么是强连通分量？在这之前先定义一个强连通性（strong connectivity）的概念：有向图中，如果一个顶点s到t有一条路径，t到s也有一条路径，即s与t互相可达，那么我们说s与t是强连通的。那么在有向图中，由互相强连通的顶点构成的分量，称作强连通分量。
一：对于kosaraju算法，这是一个比tarjan较复杂的算法，但是因为一本通上介绍了这种算法，我就找几个题目练习了一下。
kosaraju算法：可以求出强连通分量的个数，还可以对分属于不同强连通分量的点进行标记。
算法描述：（1）：第一次对图G进行DFS遍历，并在遍历的过程中，记录每一个点的退出顺序。
（2）：倒转每一条边的方向，构造一个反图G1，然后按照退出的顺序的逆序对反图进行第二次DFS遍历，
（3）：每一次遍历得到的那些点属于同一个强连通分量。
因为这就是一个不变的模板，所以直接背过就是最好了
例题：
1298. 通讯问题（来源：sojs.tk）
★ 输入文件：jdltt.in 输出文件：jdltt.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
一个篮球队有n个篮球队员，每个队员都有联系方式（如电话、电子邮件等）。但并不是每个队员的联系方式都公开，每个队员的联系方式只有一部分队员知道。问队员可以分成多少个小组，小组成员之间可以相互通知（包括一个队员一个组，表示自己通知自己）。
【输入格式】
输入文件有若干行
第一行，一个整数n，表示共有n个队员(2<=n<=100)
下面有若干行,每行2个数a、b，a、b是队员编号，表示a知道b的通讯方式。
【输出格式】
输出文件有若干行
第一行，1个整数m，表示可以分m个小组，下面有m行，每行有若干个整数，表示该小组成员编号，输出顺序按编号由小到大。
【样例输入】
- 12
- 1 3
- 2 1
- 2 4
- 3 2
- 3 4
- 3 5
- 4 6
- 5 4
- 6 4
- 7 4
- 7 8
- 7 12
- 8 7
- 8 9
- 10 9
- 11 10
【样例输出】
8
1 2 3
4 6
5
7 8
9
10
11
12
这道题目的输出顺序是很坑的。
#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define N 120
struct Edge{
int u,v,last;
}edge1[N],edge2[N];
int t=;
stack<int>s;
int ans[N][N];
int pp=;
int head1[N]={},head2[N]={};
bool visit[N]={};
int n;
void input()
{
scanf("%d",&n);
int a,b;
while(scanf("%d%d",&a,&b)==)
{
++t;
edge1[t].u=a;
edge1[t].v=b;
edge1[t].last=head1[a];
head1[a]=t;
edge2[t].u=b;
edge2[t].v=a;
edge2[t].last=head2[b];
head2[b]=t; } }
void dfs1(int k)
{
visit[k]=true;
for(int l=head1[k];l;l=edge1[l].last)
{
if(!visit[edge1[l].v])
{
dfs1(edge1[l].v);
}
}
s.push(k);
}
void dfs2(int k)
{
ans[pp][]++;
ans[pp][ans[pp][]]=k;
visit[k]=true;
for(int l=head2[k];l;l=edge2[l].last)
{
if(!visit[edge2[l].v])
{
dfs2(edge2[l].v);
}
}
}
int kosaraju()
{
while(!s.empty())
s.pop();
memset(visit,false,sizeof(visit));
for(int i=;i<=n;++i)
{
if(!visit[i])
dfs1(i);
}
memset(visit,false,sizeof(visit));
while(!s.empty())
{
int k=s.top();
s.pop();
if(!visit[k])
{
pp++;
dfs2(k);
}
}
return pp;
}
int main()
{
freopen("jdltt.in","r",stdin);
freopen("jdltt.out","w",stdout);
input();
pp=;
printf("%d\n",kosaraju());
for(int i=;i<=pp;++i)
sort(ans[i]+,ans[i]+ans[i][]+);
bool flag[N]={};
for(int i=;i<=pp;++i)
{
int q=;
int maxx=(<<);
for(int j=;j<=pp;++j)
{
if(maxx>ans[j][]&&!flag[j])
{
maxx=ans[j][];
q=j;
}
}
flag[q]=true;
for(int j=;j<=ans[q][];++j)
printf("%d ",ans[q][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return ;
}
例题二：
619. [金陵中学2007] 传话（来源cojs.tk）
★☆ 输入文件：messagez.in 输出文件：messagez.out 简单对比
时间限制：1 s 内存限制：128 MB
[问题描述]
兴趣小组的同学来自各个学校，为了增加友谊，晚会上又进行了一个传话游戏，如果 a 认识 b ，那么 a 收到某个消息，就会把这个消息传给 b ，以及所有 a 认识的人。
如果 a 认识 b ， b 不一定认识 a 。
所有人从 1 到 n 编号，给出所有“认识”关系，问如果 i 发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了 i ， 1<=i<=n 。
[输入文件]
输入文件 message.in 中的第一行是两个数 n(n<1000) 和 m(m<10000) ，两数之间有一个空格，表示人数和认识关系数。
接下来的 m 行，每行两个数 a 和 b ，表示 a 认识 b 。 1<=a, b<=n 。认识关系可能会重复给出，但一行的两个数不会相同。
[输出文件]
输出文件 message.out 中一共有 n 行，每行一个字符 T 或 F 。第 i 行如果是 T ，表示 i 发出一条新消息会传回给 i ；如果是 F ，表示 i 发出一条新消息不会传回给 i 。
[输入样例]
4 6
1 2
2 3
4 1
3 1
1 3
2 3
[输出样例]
T
T
T
F
思路：仍然是求强连通分量，只是要判断每一个人是否在一个人数>=2的强连通分量中，如果是就满足题目条件
代码：
#include<iostream>
using namespace std;
#include<cstdio>
int n,m,a,b;
struct Edge{
int u,v,last;
};
int t=;
#include<stack>
#define M 10020
Edge edge1[M],edge2[M];
#define N 1008
stack<int> s;
int head1[N],head2[N];
bool visit[N];
#include<algorithm>
#include<cstring>
bool flag[N]={};
int ans[N][N];
int calc=;
void input()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)
{
scanf("%d%d",&a,&b);
++t;
edge1[t].u=a;
edge1[t].v=b;
edge1[t].last=head1[a];
head1[a]=t;
edge2[t].u=b;
edge2[t].v=a;
edge2[t].last=head2[b];
head2[b]=t; }
}
void dfs1(int k)
{
visit[k]=true;
for(int p=head1[k];p;p=edge1[p].last)
{
if(!visit[edge1[p].v])
dfs1(edge1[p].v);
}
s.push(k);
}
void dfs2(int k)
{
int flat=calc;
visit[k]=true;
ans[calc][]++;
ans[calc][ans[calc][]]=k;
for(int p=head2[k];p;p=edge2[p].last)
if(!visit[edge2[p].v])
{ dfs2(edge2[p].v);
}
if(ans[flat][]>)/*判断每一个人是否在一个人数>=2的强连通分量*/
flag[k]=true;
}
void kosaraju()
{
while(!s.empty())
s.pop();
memset(visit,false,sizeof(visit));
for(int i=;i<=n;++i)
{
if(!visit[i])
dfs1(i);
}
memset(visit,,sizeof(visit));
while(!s.empty())
{
int k=s.top();
s.pop();
if(!visit[k])
{
calc++;
dfs2(k);
}
}
}
int main()
{
freopen("messagez.in","r",stdin);
freopen("messagez.out","w",stdout);
input();
kosaraju();
for(int i=;i<=n;++i)
if(flag[i])
printf("T\n");
else printf("F\n");
fclose(stdin);
fclose(stdout);
return ;
}