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
我太弱了 只会刷水题
这一道题比较坑就是要按照顺序输出 不止是说每一组都要排序（其实也不用排序 从1-n按顺序遍历就行 具体看代码）
针对组与组之间也要排序（其实就是按照每一组的第一个数字的大小排序，这一道题特别水 数据范围特小 写一个n^2选择排序暴力一下就过了QAQ）
代码：
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#define maxn 105
using namespace std;
vector<int> v[maxn];
int size[maxn],dfn[maxn],low[maxn],belong[maxn],st[maxn],tim,scc_cnt,cnt;
bool bein[maxn];
vector<int> ans[maxn];
void Tarjan(int rt){
dfn[rt]=low[rt]=++tim;
st[++cnt]=rt;
bein[rt]=true;
for(int i=0;i<v[rt].size();i++)
{
int to=v[rt][i];
if(!dfn[to])
Tarjan(to),low[rt]=min(low[rt],low[to]);
else if(bein[to])
low[rt]=min(low[rt],dfn[to]);
}
if(dfn[rt]==low[rt])
{
scc_cnt++;
int k;
do {
k=st[cnt];
cnt--;
bein[k]=false;
size[scc_cnt]++;
belong[k]=scc_cnt;
}while(k^rt);
}
}
int main()
{
freopen("jdltt.in","r",stdin);
freopen("jdltt.out","w",stdout);
int n,x,y;scanf("%d",&n);
while(scanf("%d%d",&x,&y)!=EOF)//读入若干行
{
v[x].push_back(y);//这是单向边啊
}
for(int i=1;i<=n;i++)
if(!dfn[i])
Tarjan(i);
printf("%d
",scc_cnt);
for(int i=1;i<=scc_cnt;i++)
{
for(int j=1;j<=n;j++)
{
if(belong[j]==i)
ans[i].push_back(j);
//printf("%d ",j);
}
//printf("
");
}
for(int i=1;i<=scc_cnt;i++)//常数小 随便乱搞
for(int j=i+1;j<=scc_cnt;j++)
if(ans[i][0]>ans[j][0])
swap(ans[i],ans[j]);
for(int i=1;i<=scc_cnt;i++)
{
for(int j=0;j<ans[i].size();j++)
printf("%d ",ans[i][j]);
printf("
");
}
return 0;
}