?? conns.txt
字號:
#include<iostream.h>
#include<fstream.h>
ifstream fin("input.txt");
ofstream fout("output.txt");
class UnionFind{
public:
UnionFind(int n);
~UnionFind(){delete[]parent;delete[]root;}
int Find(int e);
void Union(int i,int j);
private:
int *parent;
bool*root;
};
UnionFind::UnionFind(int n)
{
root=new bool [n+1];
parent=new int[n+1];
for(int e=1;e<=n;e++)
{
parent[e]=1;
root[e]=true;
}
}
int UnionFind::Find(int e)
{
int j=e;
while(!root[j]) j=parent[j];
int f=e;
while(f!=j)
{
int pf=parent[f];
parent[f]=j;
f=pf;
}
return j;
}
void UnionFind::Union(int i,int j)
{
if(parent[i]<parent[j])
{
parent[j]+=parent[i];
root[i]=false;
parent[i]=j;
}
else
{
parent[i]+=parent[j];
root[j]=false;
parent[j]=i;
}
}
void main()
{
register int i;
int n,k,m,rootname1,rootname2,u,v;
fin>>n>>k>>m;
UnionFind wgraph(n);
for(i=0;i<k;i++)
{
fin>>u>>v;
if(u!=v)
{
rootname1=wgraph.Find(u);
rootname2=wgraph.Find(v);
if(rootname1!=rootname2) wgraph.Union(rootname1,rootname2);
}
}
for(i=0;i<m;i++)
{
fin>>u>>v;
rootname1=wgraph.Find(u);
rootname2=wgraph.Find(v);
if(rootname1==rootname2) fout<<"Yes"<<endl;
else fout<<"No"<<endl;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -