#include <cstdio>int father[5001];int m,n,c,d,a;int find(int a){    return (father[a]==a) ? a : (father[a]=find(father[a]));}int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=m;i++)        father[i]=i;    int co = 0;    for (int i=1;i<=n;i++){        scanf("%d%d",&c,&d);        if (find(c)!=find(d))            father[find(c)]=find(d);            else            co++;    }    printf("%d",co);    return 0;}

 1 #include <cstdio> 2 #include <cstring> 3  4 const int maxp = 100000 + 10; 5  6 int n, m, p, f[maxp << 1]; 7 bool vis[maxp << 1], ap[maxp << 1]; 8  9 int find(int x){10     return x == f[x] ? x : f[x] = find(f[x]);11 }12 13 int main(){14     memset(ap, false, sizeof ap);15     memset(vis, false, sizeof vis);16 17     scanf("%d %d %d", &n, &m, &p);18 19     for (int i = 1; i <= n + m; i ++)20         f[i] = i;21 22     int x, y, fx, fy, ans = 0;23     for (int i = 0; i < p; i ++){24         scanf("%d %d", &x ,&y);25         ap[x] = ap[y + n] = true;26 27         fx = find(x), fy = find(y + n);28         if (fx != fy)29             f[fx] = fy;30     }31 32     for (int i = 1; i <= n + m; i ++)33         if (ap[i]){34             fx = find(i);35             if (!vis[fx])36                 vis[fx] = true, ans ++;37         }38 39     printf("%d\n", ans - 1);40 }

 1 #include <cmath> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5  6 const int maxn = 4000 + 10; 7  8 int n, m, lyd, f[maxn]; 9 10 int find(int x){11     return x == f[x] ? x : f[x] = find(f[x]);12 }13 14 bool _(int x){15     if (x == 1)16         return false;17 18     for (int i = 2; i <= sqrt(x); i ++)19         if (x % i == 0)20             return false;21 22     return true;23 }24 25 int main(){26     scanf("%d %d", &n, &m);27 28     for (int i = 1; i <= n; i ++)29         f[i] = i;30 31     int a, b, fa, fb;32     while (m --){33         scanf("%d %d", &a, &b);34         fa = find(a), fb = find(b);35         if (fa != fb)36             f[fa] = fb;37     }38 39     scanf("%d", &lyd);40 41     int flyd = find(lyd);42     a = b = 0;43     for (int i = 1; i <= n; i ++)44         if (flyd == find(i)){45             if (_(i))46                 a ++;47             else 48                 b ++;49         }50 51     printf("%d\n", min(a, b));52 }

 1 #include <cstdio> 2 int father[5001]; 3 int m,n,c,d,i,p,x,y; 4  5 int find(int a){ 6     return (father[a]==a) ? a : (father[a]=find(father[a])); 7 } 8  9 void display(bool cj){10     if (cj)11         printf("Yes\n");12     else13         printf("No\n");14 }15 16 int main(){17     scanf("%d%d%d",&m,&n,&p);18     for (i=1;i<=m;i++)19         father[i]=i;20 21     for (i=1;i<=n;i++){22         scanf("%d%d",&c,&d);23         father[find(c)]=find(d);    24     }25 26     for (i=1;i<=p;i++){27         scanf("%d%d",&x,&y);28         bool apple=false;29         if (find(x)==find(y))30             apple=true;31         display(apple);32     }33 34     return 0;35 }

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 const int mod = 100007; 7 const int maxn = 300000; 8 const int maxm = 10000 + 10; 9 10 char buff[10];11 int n, m, hash[mod + 2], len[maxn + 2], f[maxn + 2];12 13 inline int get_hash(int x){14     int ret = x % mod;15     while (hash[ret] ^ -1 && hash[ret] ^ x)16         ret = (ret + 1) % mod;17 18     hash[ret] = x;19 20     return ret;21 }22 23 inline int find(int x){24     if (f[x] ^ x){25         int temp = f[x];26         f[x] = find(temp);27         len[x] = (len[x] + len[temp] + 2) & 1;28     }29 30     return f[x];31 }32 33 inline bool legal(int a, int b, int type){34     int fa = find(a), fb = find(b), temp = len[a] - len[b] + 2;35 36     if (fa ^ fb){37         //link a and b38         f[fb] = fa, len[fb] = (temp + type) & 1;39         return true;40     }41 42     else if ((temp & 1) ^ type)43         return false;44         45     return true;46 }47 48 int main(){49     memset(hash, -1, sizeof hash);50 51     scanf("%d %d", &n, &m);52 53     for (int i = 1; i <= maxn; i ++)54         f[i] = i;55 56     for (int i = 1, l, r, type; i <= m; i ++){57         scanf("%d %d %s", &l, &r, buff);58         type = buff[0] == ‘o‘;59     60         if (!legal(get_hash(l - 1), get_hash(r), type)){61             printf("%d\n", i - 1);62             return 0;63         }64     }65 66     printf("%d\n", m);67 }

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 const int maxl = 26 + 10; 7 const int maxn = 10000 + 10; 8 const char T[maxl] = "poison"; 9 10 int n, m, q, ne = 0;11 bool p[maxn], vis[maxn];12 char a[maxl], b[maxl], c[maxl], s[maxl * 3];13 14 struct Edge {15     int to;16     Edge *next;17 } *head[maxn], e[maxn * 10];18 19 void add_edge(int f, int to){20     e[ne].to = to;21     e[ne].next = head[f];22     head[f] = e + ne ++;23 }24 25 bool match(int st){26     for (int i = st, j = 0; j < 6; i ++, j ++)27         if (s[i] != T[j])28             return false;29 30     return true;31 }32 33 bool check(){34     int len = strlen(s);35 36     for (int i = 0; i < len; i ++)37         s[i] = c[s[i] - ‘a‘];38 39     for (int i = 0; i <= len - 6; i ++)40         if (match(i))41             return true;42         43     return false;44 }45 46 void dfs(int now){47     vis[now] = true;48     for (Edge *p = head[now]; p; p = p->next)49         if (!vis[p->to])50             dfs(p->to);51 }52 53 int main(){54     memset(p, false, sizeof p);55     memset(vis, false, sizeof vis);56 57     scanf("%s %s %d %d", a, b, &n, &m);58 59     for (int i = 0; i < 26; i ++)60         c[a[i] - ‘a‘] = b[i];61 62     int v, u, id, ans = 0;63     for (int i = 0; i < m; i ++){64         scanf("%d %s", &id, s);65         if (check())66             p[id] = true;67     }68 69     scanf("%d", &q);70     for (int i = 0; i < q; i ++){71         scanf("%d %d", &u, &v);72         add_edge(u, v);73         add_edge(v, u);74     }75     76     for (int i = 1; i <= n; i ++)77         if (p[i] && !vis[i])78             dfs(i);79 80     for (int i = 1; i <= n; i ++)81         if (!vis[i])82             ans ++;83 84     printf("%d\n", ans);85 }

 1 #include <cstdio> 2  3 const int MAXN = 50000*3+10; 4  5 int ans,n,m,f[MAXN]; 6  7 inline int find(int x){ 8     return (f[x]==x) ? x : f[x]=find(f[x]); 9 }10 11 inline void link(int x,int y){12     f[find(x)] = find(y);13 }14 15 inline int cal(){16     int a1,a2,a3,b1,b2,b3,a,b,d;17     scanf("%d %d %d",&d,&a,&b);18     if ((d==2 && a==b) || a>n || b>n) return 1;19     a1 = find(a),a2 = find(a+n),a3 = find(a+n+n);20     b1 = find(b),b2 = find(b+n),b3 = find(b+n+n);21 22     if (d==1 && a1!=b3 && a1!=b2 && b1!=a2 && b1!=b3){ 23         link(a,b),link(a+n,b+n),link(a+n+n,b+n+n);24         return 0;25     }26     if (d==1) return 1;27     if (d==2 && a1!=b1 && a2!=b1 && b3!=a1){ 28         link(a,b2),link(a3,b1),link(a2,b3);29         return 0;30     }31     return 1;32 }33 34 int main(){35     scanf("%d%d",&n,&m),ans = 0;36     for (int i=1;i<=3*n;i++) 37         f[i] = i;38     while (m--) 39         ans += cal();40     printf("%d\n",ans);41 }

 1 #include <cstdio> 2  3 const int MOD = 1000000009; 4 const int MAXN = 200000+10; 5  6 int n,m,u,v,f[MAXN]; 7  8 inline int find(int x){ 9     return (f[x]==x) ? x : f[x]=find(f[x]);10 }11 12 int main(){13     scanf("%d%d",&n,&m);14     15     for (int i=1;i<=n;i++) 16         f[i] = i;17     18     int ans=0;19     while (m--){20         scanf("%d%d",&u,&v);21         if (find(u)==find(v)) ans *= 2,ans++,ans %= MOD;22         else f[find(u)] = find(v);23         printf("%d\n",ans);24     }25     return 0;26 }

 1 #include <cstdio> 2 #define gc inputCh=getchar(); 3 #define isDig (48<=inputCh&&inputCh<=57) 4 #define nextInt ({int _ = 0; do gc while(!isDig); do _ *= 10, _ += inputCh-48, gc while (isDig); _;}) 5 using namespace std; 6  7 const int maxn = 1e5 + 10; 8  9 char inputCh;10 int n, m, k, f[maxn];11 12 struct Edge {13     int u, v;14 } e[maxn << 1];15 16 int find(int x){17     return x == f[x] ? x : f[x] = find(f[x]);18 }19 20 int main(){21     n = nextInt, m = nextInt, k = nextInt;22 23     for (int i = 1; i <= n; i ++)24         f[i] = i;25 26     int u, v, fu, fv, tot = 0;27     for (int i = 1; i <= m; i ++){28         u = nextInt, v = nextInt;29 30         if (u > k && v > k){31             fu = find(u), fv = find(v);32             if (fu != fv)33                 f[fu] = fv;34         }35 36         else37             e[tot].u = u, e[tot].v = v, tot ++;38     }39 40     int ans = 0;41     for (int i = 0; i < tot; i ++){42         fu = find(e[i].u), fv = find(e[i].v);43             if (fu != fv)44                 f[fu] = fv;    45             else46                 ans ++;47     }48 49     printf("%d\n", ans);50 }