Cogs 1298.通讯问题

2023-12-25 16:38

文章标签 问题通讯 cogs 1298

本文主要是介绍Cogs 1298.通讯问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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模板+缩点+sort
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define MAXN 101
using namespace std;
struct data
{int v,next;
}
e[MAXN];
//vector<int>g[MAXN];
struct node
{int x[500];int l;
}
g[MAXN];
int n,m,cut,belong[MAXN],head[MAXN],dfn[MAXN],stack[MAXN],low[MAXN],in[MAXN],top,tot;
void init()
{cut=tot=top=0;memset(head,-1,sizeof(head));memset(stack,0,sizeof(stack));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(in,0,sizeof(in));
}
void add_edge(int u,int v)
{e[tot].v=v;e[tot].next=head[u];head[u]=tot++;
}
void tarjan(int u)
{int v;low[u]=dfn[u]=++cut;in[u]=1;//当前节点进栈stack[top++]=u; for(int i=head[u];i!=-1;i=e[i].next)//遍历边{v=e[i].v;if(!dfn[v])//未被访问 {tarjan(v);low[u]=min(low[u],low[v]);}else if(in[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u])//找到一个强联通分量的根 {int l=0,a[MAXN];tot++;do{v=stack[--top];//退栈in[v]=0;belong[v]=tot;//tot为连通分量编号 a[++l]=v;}while(u!=v);sort(a+1,a+l+1);for(int i=1;i<=l;i++){g[tot].x[i]=a[i];}g[tot].l=l;}
}int cmp1(const node &x,const node &y)
{return x.x[1]<y.x[1];
}
int main()
{//freopen("jdltt.in","r",stdin);//freopen("jdltt.out","w",stdout);while(scanf("%d",&n)!=EOF){int x,y;init();for(int i=1;i<=n;i++)g[i].l=0;while(scanf("%d %d",&x,&y)!=EOF){add_edge(x,y);}tot=0;for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}cout<<tot<<endl;sort(g+1,g+tot+1,cmp1);for(int i=1;i<=tot;i++){for(int j=1;j<=g[i].l;j++)printf("%d ",g[i].x[j]);printf("\n");}}return 0;
}