tarjan算法--cojs 1298. 通讯问题

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行，每行有若干个整数，表示该小组成员编号，输出顺序按编号由小到大。

【样例输入】

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

【样例输出】

1 2 3

4 6

7 8

  1 /*先进行tarjan把所有的强连通分量放到几个数组中去，然后先对每个数组中的元素按字典序排序，然后把几个数组按照字典序排序，这样才能按照题目的意思输出*/
  2 #include<iostream>
  3 using namespace std;
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<stack>
  7 stack<int>sta;
  8 #include<algorithm>
  9 #define N 120
 10 int dfn[N],low[N];
 11 int n,anst=0;
 12 struct Ans{
 13     int a[N];
 14     void sor(){sort(a+1,a+a[0]+1);}
 15 }ans[N];
 16 struct Edge{
 17     int v,last;
 18 }edge[N*N*2];
 19 int topt=0,t=0;
 20 int head[N];
 21 bool visited[N]={0},instack[N]={0};
 22 void add_edge(int u,int v)
 23 {
 24     ++t;
 25     edge[t].v=v;
 26     edge[t].last=head[u];
 27     head[u]=t;
 28 }
 29 void input()
 30 {
 31     scanf("%d",&n);
 32     int u,v;
 33     while(scanf("%d%d",&u,&v)==2)
 34     {
 35         add_edge(u,v);
 36     }
 37 }
 38 void tarjan(int k)/*tarjan算法，不解释*/
 39 {
 40     visited[k]=true;
 41     dfn[k]=low[k]=++topt;
 42     sta.push(k);
 43     instack[k]=true;
 44     for(int l=head[k];l;l=edge[l].last)
 45     {
 46         if(!visited[edge[l].v])
 47         {
 48             tarjan(edge[l].v);
 49             low[k]=min(low[k],low[edge[l].v]);  
 50         }
 51         else {
 52             if(instack[edge[l].v])
 53               low[k]=min(low[k],dfn[edge[l].v]);
 54         }
 55         
 56     }
 57     if(low[k]==dfn[k])
 58     {
 59         anst++;
 60         int ys=sta.top();
 61         instack[ys]=false;
 62         sta.pop();
 63         while(ys!=k)
 64         {
 65             ans[anst].a[0]++;
 66             ans[anst].a[ans[anst].a[0]]=ys;
 67             ys=sta.top();
 68             instack[ys]=false;
 69             sta.pop();
 70         }
 71         instack[ys]=false;
 72         ans[anst].a[0]++;
 73         ans[anst].a[ans[anst].a[0]]=ys;
 74     }
 75 }
 76 int cmp(Ans p,Ans q)
 77 {
 78     for(int i=1;i<=p.a[0]&&i<=q.a[0];++i)
 79     {
 80         if(p.a[i]<q.a[i])
 81           return true;
 82     }
 83     return false;
 84 }
 85 int main()
 86 {
 87     freopen("jdltt.in ","r",stdin);
 88     freopen("jdltt.out","w",stdout);
 89     input();
 90     for(int i=1;i<=n;++i)
 91       if(!visited[i])
 92         tarjan(i);
 93     for(int i=1;i<=anst;++i)
 94        ans[i].sor();/*对每个强连通分量的元素排序，注意结构体函数的妙用*/
 95     sort(ans+1,ans+anst+1,cmp);/*再把所有的强连通分量排序*/
 96     printf("%d
",anst);
 97     for(int i=1;i<=anst;++i)
 98     {
 99         for(int j=1;j<=ans[i].a[0];++j)
100           printf("%d ",ans[i].a[j]);
101         printf("
");
102     }
103     fclose(stdin);fclose(stdout);
104     return 0;
105 }