cojs 1298. 通讯问题
★ 输入文件：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
/*先进行tarjan把所有的强连通分量放到几个数组中去，然后先对每个数组中的元素按字典序排序，然后把几个数组按照字典序排序，这样才能按照题目的意思输出*/
#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<stack>
stack<int>sta;
#include<algorithm>
#define N 120
int dfn[N],low[N];
int n,anst=;
struct Ans{
int a[N];
void sor(){sort(a+,a+a[]+);}
}ans[N];
struct Edge{
int v,last;
}edge[N*N*];
int topt=,t=;
int head[N];
bool visited[N]={},instack[N]={};
void add_edge(int u,int v)
{
++t;
edge[t].v=v;
edge[t].last=head[u];
head[u]=t;
}
void input()
{
scanf("%d",&n);
int u,v;
while(scanf("%d%d",&u,&v)==)
{
add_edge(u,v);
}
}
void tarjan(int k)/*tarjan算法，不解释*/
{
visited[k]=true;
dfn[k]=low[k]=++topt;
sta.push(k);
instack[k]=true;
for(int l=head[k];l;l=edge[l].last)
{
if(!visited[edge[l].v])
{
tarjan(edge[l].v);
low[k]=min(low[k],low[edge[l].v]);
}
else {
if(instack[edge[l].v])
low[k]=min(low[k],dfn[edge[l].v]);
} }
if(low[k]==dfn[k])
{
anst++;
int ys=sta.top();
instack[ys]=false;
sta.pop();
while(ys!=k)
{
ans[anst].a[]++;
ans[anst].a[ans[anst].a[]]=ys;
ys=sta.top();
instack[ys]=false;
sta.pop();
}
instack[ys]=false;
ans[anst].a[]++;
ans[anst].a[ans[anst].a[]]=ys;
}
}
int cmp(Ans p,Ans q)
{
for(int i=;i<=p.a[]&&i<=q.a[];++i)
{
if(p.a[i]<q.a[i])
return true;
}
return false;
}
int main()
{
freopen("jdltt.in ","r",stdin);
freopen("jdltt.out","w",stdout);
input();
for(int i=;i<=n;++i)
if(!visited[i])
tarjan(i);
for(int i=;i<=anst;++i)
ans[i].sor();/*对每个强连通分量的元素排序，注意结构体函数的妙用*/
sort(ans+,ans+anst+,cmp);/*再把所有的强连通分量排序*/
printf("%d\n",anst);
for(int i=;i<=anst;++i)
{
for(int j=;j<=ans[i].a[];++j)
printf("%d ",ans[i].a[j]);
printf("\n");
}
fclose(stdin);fclose(stdout);
return ;
}