Communication【floyd判环+并查集】
Communication
题目描述
The Ministry of Communication has an extremely wonderful message system, designed by the President himself. For maximum efficiency, each office in the Ministry can send a message directly to some, but not necessarily all, other offices. These connections are not always two-way, because sometimes one office should have the power to send a message to another office, but the other office should not have the power to send one back. This may seem unfair, or even illogical, to uneducated people, but this is the will of the President.
There are so many offices now that the situation has become rather confusing, so the President has decided to reorganize the Ministry to be better adapted to the message system.
The President will divide the Ministry into new departments based on two simple principles:
1. If A and B are in the same department then A can transmit a message to B, and B can transmit a message to A.
2. If A can transmit a message to B, and B can transmit a message to A, then A and B are in the same department.
How many departments will the reorganized Ministry have?
输入
Input starts with a line containing a single integer N, with 0 < N ≤ 100. This tells you how many test cases there will be.
Each following pair lines contains a single test case. The first line of each test case contains an integer n, with 1 < n ≤ 200. This is the number of offices the Ministry has. The second line starts with an integer e with 0 < e <n2/4. This tells you how many individual direct (and directed) connections the Ministry has. Following this are e pairs of integers a, b, with 0 ≤a < b ≤ n − 1. These pairs indicate that there is a connection from a to b. There is at most one direct connection going out from one office and into another.
输出
Each line of output is an integer saying how many departments the Ministry corresponding to that test case will have.
样例输入
3 6 2 0 5 5 0 5 7 0 1 0 2 1 0 1 3 2 4 3 1 4 2 3 4 0 1 0 2 1 0 1 2
样例输出
5 2 2
题意：
T组数据 每组先输入一个数n表示共n个点 然后是m和m组关系 （a，b）表示a可以给b发消息 如果满足以下条件的一种 则可以将他们划分到一组：
1、1-->2 && 2-->1 (相互之间可以直接通信)
2、1-->2 && 2-->3 && 3-->1 （成环）（题意中没说明 只考虑1WA了所以想到可能有这种情况）
最后输出可以分成几组
思路：
先标记那两个点之间有关系 因为想使用并查集 但并查集的边是无方向的 所以必须满足两点之间可以相互通话才使用并查集连接
分两种情况对待1、2的判断条件：
1、如果f[i][j]=1&&f[j][i]=1说明他们符合条件1并且是双向的边 那就可以把它们放进并查集
2、条件是成环 所以用floyd先判断是否成环：如果成环 则dis[i][j]和dis[j][i]一定是小于初始化的值的 也把他们放进并查集
最后跑for 判断有几个点的pre[i]==i 输出个数即可
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e2;
const int INF=0x3f3f3f3f;
int n,m;
int f[MAX+5][MAX+5];
int pre[MAX+5];
int dis[MAX+5][MAX+5];
void floyd()
{
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dis[i][j]>dis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
int judge(int i, int j)
{
if(dis[i][j]<INF&&dis[j][i]<INF){
return 1;
}
return 0;
}
int fd(int x)
{
int r=x;
while(pre[r]!=r){
r=pre[r];
}
return r;
}
void mix(int x,int y)
{
int fx=fd(x),fy=fd(y);
if(fx!=fy){
pre[fx]=fy;
}
}
void init()
{
for(int i=0;i<MAX;i++){
pre[i]=i;
for(int j=0;j<MAX;j++){
f[i][j]=0;
dis[i][j]=INF;
}
}
}
struct node{
int u;
int v;
}a[MAX+5];
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
a[i].u=u,a[i].v=v;
f[u][v]=1;
dis[u][v]=1;
}
floyd();
for(int i=0;i<m;i++){
int u=a[i].u,v=a[i].v;
if(f[v][u]==1||judge(u,v)){
mix(u,v);
}
}
int ans=0;
for(int i=0;i<n;i++){
if(pre[i]==i){
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}