std.cpp

#include<iostream>
#include<vector>

using namespace std;
const int MAXN = 5000000;
const int MAXM = 5000000;
int n,m,q;
int fa[MAXN+5];
int findFa(int x){
	if(x==fa[x])
		return x;
	return fa[x]=findFa(fa[x]);
}
vector<int> e[MAXN+5];//随意生成树 
vector<pair<int,int> > ee;//非树边 
int dep[MAXN+5];//e上每点深度
int faE[MAXN+5];//e上每点父节点 
void dfs(int u,int fa){
	faE[u] = fa; 
	for(int i = 0; i < e[u].size();i++){
		int v = e[u][i];
		if(v == fa)
			continue;
		dep[v] = dep[u]+1;
		dfs(v,u);
	}
} 
int ans;//桥的数量 
//连接 x~y 并更新桥数 ans 
void line(int x, int y){
	while(x != y){
		//cout<<ans<<":"<<x<<" "<<y<<" ";
		if(x != fa[x])
			x = findFa(x);
		if(y != fa[y])
			y = findFa(y);
		//cout<<x<<"~"<<y<<"\n";
		if(x == y)
			break;
		if(dep[y] >= dep[x])
		{
			fa[y] = faE[y];
			y = faE[y];
			ans--;
		}
		if(dep[x] > dep[y])
		{
			fa[x] = faE[x];
			x = faE[x];
			ans--;
		}
		//cout<<ans<<"="<<x<<"~"<<y<<"\n";
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//int caseId=0;
	while(cin>>n>>m){
		if(n==0&&m==0)
			break;
		//cout<<"Case "<<++caseId<<":\n";
		//初始化 
		for(int i=1;i<=n;i++){
			fa[i]=i;
			e[i].clear();
		}
		ee.clear();
		//输入边，找到生成树与非树边 
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			int faU = findFa(u);
			int faV = findFa(v);
			if(faU!=faV)
			{
				e[u].push_back(v);
				e[v].push_back(u);
				fa[faU] = faV;
			}else{
				ee.push_back(make_pair(u,v));
			}
		} 
		//dfs 求树上每点深度
		dep[1]=1;
		dfs(1,0); 
		/*
		cout<<"dep:";
		for(int i=1;i<=n;i++)
			cout<<dep[i]<<" ";
		cout<<"\n"; 
		cout<<"faE:";
		for(int i=1;i<=n;i++)
			cout<<faE[i]<<" ";
		cout<<"\n"; 
		*/
		//重置并查集 
		for(int i=1;i<=n;i++)
			fa[i] = i;
		ans=n-1;
		//连接初始非树边 
		for(int i = 0; i < ee.size(); i++){
			pair<int,int> nowE = ee[i]; 
			int x = nowE.first;
			int y = nowE.second;
			int faX = findFa(x);
			int faY = findFa(y);
			if(faX == faY)
				continue;
			line(x, y);//连接 
		} 
		cin>>q;
		while(q--){
			int x,y;
			cin>>x>>y; 
			int faX = findFa(x);
			int faY = findFa(y);
			if(faX == faY){
				cout<<ans<<"\n";
				continue;
			}
			line(x, y);//连接 
			cout<<ans<<"\n";
		} 
		//cout<<"\n";
	}
	return 0;
} 

gen.py

from cyaron import *
for i in range(1, 8):
    print(i)
    test_data = IO(file_prefix="", data_id=i)
    if i <= 3:
        n=randint(900,1000)
        m=randint(n-1,1000)
        q=randint(900,1000)
    elif i<=7:
        n=randint(199900,200000)
        m=randint(n-1,200000)
        q=randint(199900,200000)
    else:
        n=randint(4999900,5000000)
        m=randint(n-1,5000000)
        q=randint(4999900,5000000)
    test_data.input_writeln(n, m)
    graph = Graph.UDAG(n, m)
    test_data.input_writeln(graph.to_str(output=Edge.unweighted_edge))
    test_data.input_writeln(q)
    for j in range(q):
        test_data.input_writeln(randint(1,n),randint(1,n))
    test_data.output_gen("std.exe")