基础代码-维护图的连通性

问题 D: 维护图的连通性

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给定一个无向图 G,写一个程序处理以下两种操作:

1. 删去一条边 (u, v)

2. 询问两点 u,v是否连通  

输入

输入文件的第一行包含三个整数 n,m,q,依次代表图的顶点数、边数、 询问的个数。

接下来 m 行,每行两个整数 u,v,描述图中的一条边(u, v)。接下来q 行,每行三个整数t,u,v,描述一个操作。若t = 1 则操作代表删去边 (u, v),否则操作代表询问点u 和 v 是否连通。数据保证删除的边一定存 在。 

输出

对于每个询问操作输出一行字符串 “Yes”(连通)或者“No”(不连通)。  

样例输入

3 2 4
1 2
2 3
2 1 2
1 1 2
2 1 3
2 2 3

样例输出

Yes
No
Yes

提示

对于所有的数据, n ≤ 1000,m ≤ 100000, q≤ 100000,可能存在重边。 

正难则反。先将图构建好后，将要删除的边先删去，然后从最后一个询问开始处理，若t[i]=1则将这条边连上，若t[i]=2则判断u与v是否连通。用并查集维护连通性。

Code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define M 101000
#define N 1100
#define Q 101000
using namespace std;
int u[M],v[M],t[Q],x[Q],y[Q],f[N],mat[N][N],flag[Q];
inline int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
inline void unionn(int x,int y)
{
    int fax=find(x),fay=find(y);
    if(fax!=fay) f[fax]=fay;
}
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        mat[u[i]][v[i]]++;
        mat[v[i]][u[i]]++;
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
        if(t[i]==1){mat[x[i]][y[i]]--;mat[y[i]][x[i]]--;}
    }
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++)
        if(mat[x[i]][y[i]])
        {
            int fx=find(x[i]),fy=find(y[i]);
            if(fx!=fy) f[fx]=fy;
        }
    for(int i=q;i;i--)
    {
        if(t[i]==1){unionn(x[i],y[i]);flag[i]=-1;}
        else{
            int fax=find(x[i]),fay=find(y[i]);
            if(fax==fay) flag[i]=1;else flag[i]=0;
        }
    }
    for(int i=1;i<=q;i++)
        if(!flag[i]) puts("No");
        else if(flag[i]==1) puts("Yes");
    return 0;
}