首页 > 代码库 > COGS 1298. 通讯问题
COGS 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 <ctype.h>#include <cstdio>#define N 10050void read(int &x){ x=0;bool f=0; register char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; x=f?(~x)+1:x;}struct Edge{ int next,to; Edge (int next=0,int to=0) :next(next),to(to) {}}edge[N<<1];bool vis[N],instack[N];int tim,sumcol,col[N],n,head[N<<1],cnt,dfn[N],low[N],stack[N],top;int min(int a,int b) {return a>b?b:a;}void insert(int u,int v){ edge[++cnt]=Edge(head[u],v); head[u]=cnt;}void tarjan(int x){ dfn[x]=low[x]=++tim; instack[x]=true; stack[++top]=x; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(instack[v]) low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { sumcol++; int t; do { t=stack[top--]; instack[t]=false; col[t]=sumcol; }while(x!=t); }}int main(){ freopen("jdltt.in","r",stdin);freopen("jdltt.out","w",stdout); read(n);int x,y; while(scanf("%d%d",&x,&y)!=EOF) insert(x,y); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); printf("%d\n",sumcol); for(int i=1;i<=n;i++) { if(!vis[i]) { for(int j=i;j<=n;j++) { if(col[j]==col[i]) { vis[j]=1; printf("%d ",j); } } printf("\n"); } } return 0;}
COGS 1298. 通讯问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。