#include<bits/stdc++.h>
using namespace std;
/*并查集，开辟一个大数组*/
const int MAXN=1000001;
int father[MAXN];
int appear[MAXN];//1表示appear[i]出现过
void Initial()
{
    for(int i=0;i<MAXN;i++)
    {
        father[i]=-1;
        appear[i]=0;
    }
}
int Find(int x)
{
    while(father[x]!=-1)
        x=father[x];
    return x;
}
void Union(int x,int y)//根节点的合并集合
{
    x=Find(x);
    y=Find(y);
    if(x!=y)
       father[y]=x;
    return ;
}
int main()
{
    int x,y;
    Initial();
    while(cin>>x>>y)
    {
        Union(x,y);
        appear[x]=1;
        appear[y]=1;
        //x和y出现过则置为1
    }
    int component=0;
    for(int i=0;i<MAXN;i++)
        if(appear[i]==1&&father[i]==-1)
            component++;
    //因为之前合并过集合所以father[i]==-1说明有一个连通分量，且要出现过
    cout<<component<<endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
#include <sstream>
#include<map>
using namespace std;
int fa[1000005];
bool vis[1000005];
int get(int root){
    if(fa[root]==root)
        return root;
    else
        return fa[root]=get(fa[root]);
}
int main(){
    int a,b;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=1000000;i++)
        fa[i]=i;
    while(cin>>a>>b){
        vis[a]=true;
        vis[b]=true;
        a=get(a);
        b=get(b);
        fa[a]=b;
    }
    int ans=0;
    for(int i=0;i<=1000000;i++){
        if(vis[i]==true){

            if(fa[i]==i)
                ans++;
        }
    }
    cout<<ans<<endl;
}

/*
*根据输入的数据生成并查集 ， 然后查询根节点的个数
*/


#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6;
int father[maxn+5];

void Initial()   //初始化父节点数组
{
    for(int i = 0;i < maxn; i++) father[i] = i;
}

int getFather(int x)   //找到根节点
{
    int a = x;
    while(x != father[x]) x = father[x];
    //路径压缩
    while(a != father[a])
    {
        int z = a; a = father[a]; father[z] = x;
    }
    return x;
}

void Union(int a, int b)   //合并
{
    int fa = getFather(a);
    int fb = getFather(b);
    if(fa != fb) father[fa] = fb;
}

int main()
{
    ios::sync_with_stdio(false);
    int a, b; set<int> s;
    Initial();
    while(cin >> a >> b)
    {
        Union(a, b); s.insert(a); s.insert(b);
    }

    int ans = 0;   
    for(int i : s) ans += father[i] == i? 1 : 0;
    cout << ans << "\n";

    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <set>
using namespace std;
map<int, bool> visit;
map<int, vector<int> > mp;
void dfs(int x)
{
    visit[x] = 1;
    for(int i = 0;i<mp[x].size();i++)
    {
        if(!visit[mp[x][i]])
        dfs(mp[x][i]);
    }
}
int main()
{
    visit.clear();
    mp.clear();
    set<int> st;
    st.clear();
    int x,y;
    while(cin >> x >> y)
    {
        st.insert(x);
        st.insert(y);
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    int ans = 0 ;
    for(set<int>::iterator it = st.begin() ; it != st.end(); ++it)
    {
        if(visit[*it] == 0)
        {
            ans++;
            dfs(*it);
        }
    }
    cout << ans << endl;
}

/*
DFS
1.只有有边的点参与计算联通分支数，所以将vis默认为true，当有输入边时，设顶点为false，就可以只考虑有边的顶点的DFS。
2.顶点最大数量MAXN至少设置1000010。100010都不行。
*/
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN=1000010;
vector<int> Adj[MAXN];
bool vis[MAXN];
void DFS(int u)
{
    vis[u]=true;
    for(int i=0;i<Adj[u].size();i++)
    {
        int v=Adj[u][i];
        if(vis[v]==false)
            DFS(v);
    }
}
int main()
{
    fill(vis,vis+MAXN,true);
    int v1,v2;
    while(scanf("%d%d",&v1,&v2)!=EOF)
    {
        Adj[v1].push_back(v2);
        Adj[v2].push_back(v1);
        //只有有边的点参与计算联通分支数
        vis[v1]=vis[v2]=false;
    }
    int count=0;
    for(int i=0;i<MAXN;i++)
    {
        if(vis[i]==false)
        {
            DFS(i);
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}

#include <iostream>
#include <set>
using namespace std;
#define N 1000000
int Tree[N];
int findRoot(int x){
    if(Tree[x]==-1) return x;
    int temp=findRoot(Tree[x]);
    Tree[x]=temp;
    return temp;
}
int main(){
    int a,b;
    set<int>s;
    for(int i=0;i<N;i++) Tree[i]=-1;
    while(cin>>a>>b){
        s.insert(a);
        s.insert(b);
        a=findRoot(a);
        b=findRoot(b);
        if(a!=b) Tree[a]=b;
    }
    int ans=0;
    set<int>::iterator it;
    for(it=s.begin ();it!=s.end ();it++)
        if(Tree[*it]==-1) ans++;
    cout<<ans<<endl;
    return 0;
}

DFS 染色，一次染一个联通集

#include <functional>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    unordered_map<int, vector<int>> g;
    unordered_set<int> st;
    int a, b;
    while (cin >> a >> b) {
        st.insert(a);
        st.insert(b);
        if (a == b) continue;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    unordered_map<int, bool> vis;
    vector<int> nodes(st.begin(), st.end());
    for (auto& [k, v]: g) vis[k] = false;

    function<void(int, int)> dfs = [&](int cur, int pre) {
        if (vis[cur] == true) return;
        vis[cur] = true;
        for (auto nxt: g[cur]) {
            if (nxt != pre && !vis[nxt]) {
                dfs(nxt, cur);
            }
        }
    };

    int ans = 0;
    for (int & node : nodes) {
        if (!vis[node]) {
            dfs(node, -1);
            ans++;
        }
    }
    cout << ans;
}

正经做法

#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>

using namespace std;

int top[2000001], setRank[2000001]; //数据范围一定要够大，有点毒瘤了
set<int> nodeSet;

void init(int x) {
    for(int i = 1; i <= x; i++) {
        top[i] = i;
        setRank[i] = 0;
    }
}

//非递归写法，常数有所优化
int find(int x)
{
    while(top[x] != x)
    {
        int t = x;
        x = top[x];
        top[t] = top[x];
    }
    return x;
}


void set_union(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx != fy) {
        if(setRank[fx] > setRank[fy]) top[fy] = fx;
        else if(setRank[fx] < setRank[fy]) top[fx] = fy;
        else top[fy] = fx, setRank[fx] ++;
    }
}

int main() {
    int m, n;
    int max_num = -1;
    init(2000000);
    while(cin >> m >> n) {
        nodeSet.insert(m);
        nodeSet.insert(n);
        set_union(m, n);
    }
    int cnt = 0;
    for(auto i : nodeSet) {
        if(find(i) == i) cnt++;
    }
    cout << cnt << endl;
	return 0;
}

use std::io::{self, *};
 
fn main() {
    println!("26202");
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
vector<int> father(N, 0);

int find(int u){
    return father[u] == -1 ? u : father[u] = find(father[u]);
}

void join(int u, int v){
    u = find(u);
    v = find(v);
    if( u == v) return;
    else father[v] = u;
}

int main() {
    int u, v;

    while(cin>>u>>v){
        if(father[u] == 0) father[u] = -1;
        if(father[v] == 0) father[v] = -1;
        join(u, v);
    }

    int count = 0;
    for(int i = 0; i < N; i++){
        if(father[i] == -1) count++;
    }
    cout<<count<<endl;
}

#include <cstdint>
#include <iostream>
#include<vector>
#include<map>
using namespace std;
map<int,int>node;
struct pairnode{
    int first;
    int second;
    pairnode(int _first,int _second){
        first=_first;
        second=_second;
    }
};
void Init(int visit[],int n){
    for(int i=0;i<n;i++){
        visit[i]=i;
    }
}
int findfather(int visit[],int n){
    if(visit[n]==n){
        return n;
    }
    else return findfather(visit,visit[n]);
}
int main() {
    vector<pairnode> v;
    int a, b;
    int i=0;
    int u, w;
    while (cin >> a >> b) {
        if (node.count(a) == 0) {
            node.insert({a,i++});
        }
        if (node.count(b) == 0) {
            node.insert({b,i++});
        }
        pairnode p(a, b);
        v.push_back(p);
    }
    int setnode = node.size();
    int visit[setnode];
    Init(visit,setnode);
    for (i = 0; i < v.size(); i++) {
        u = v[i].first;
        w = v[i].second;
        int uroot = findfather(visit,node[u]);
        int wroot = findfather(visit,node[w]);
        if (uroot != wroot) {
            setnode--;
            visit[wroot]=uroot;
        }
    }
    cout << setnode << endl;
    return 0;
}

import sys

nodes = set()
edges = []

for line in sys.stdin:
    start, end = list(map(int, line.strip().split()))
    nodes.add(start)
    nodes.add(end)
    edges.append([start, end])
    edges.append([end, start])

nodes = list(nodes)
adjusts = {}
isvisited = {}
for node in nodes:
    adjusts[node] = []
    isvisited[node] = False

for start, end in edges:
    if start == end:
        pass
    else:
        adjusts[start].append(end)

count = 0
for node in nodes:
    if not isvisited[node]:
        count += 1
        queue = [node]
        while len(queue) > 0:
            cur = queue[0]
            queue.pop(0)
            for next_node in adjusts[cur]:
                if not isvisited[next_node]:
                    queue.append(next_node)
                    isvisited[next_node] = True

print(count)