vector<int> fd(N, 0);
int find(int num) {
if (fd[num] == num) {
return num;
} else {
return fd[num] = find(fd[num]);
}
}class DSU {
private:
vector<int> parent;
vector<int> rank;
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
void init(){
for (int i = 0; i < parent.size(); ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) {
parent[x] = y;
} else {
parent[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}
bool isConnected(int x, int y) {
return find(x) == find(y);
}
};#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N],deep[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:find(fa[x]);}
inline void merge(Re x,Re y){
x=find(x),y=find(y);
if(x==y)return;
if(deep[x]==deep[y])++deep[fa[x]=y];
else if(deep[x]>deep[y])fa[y]=x;
else fa[x]=y;
}
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)fa[i]=i;
while(T--){
in(op),in(x),in(y);
if(op<2)merge(x,y);
else puts(find(x)==find(y)?"Y":"N");
}
}
#include<algorithm>
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N],size[N],deep[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:find(fa[x]);}
inline void merge(Re x,Re y){
x=find(x),y=find(y);
if(x==y)return;
if(size[x]>size[y])std::swap(x,y);
fa[x]=y,size[y]+=size[x];
}
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)fa[i]=i,size[i]=1;
while(T--){
in(op),in(x),in(y);
if(op<2)merge(x,y);
else puts(find(x)==find(y)?"Y":"N");
}
}
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)fa[i]=i;
while(T--){
in(op),in(x),in(y);
if(op<2){if(find(x)!=find(y))fa[find(x)]=find(y);}
else puts(find(x)==find(y)?"Y":"N");
}
}
#include<cstdio>
#include<iostream>
using namespace std;// 找图的最小环
int minn=0x7fffff,n,f[200005],d[200005];
inline int min(int a,int b){if(a>b) return b;else return a;}
inline int find(int x){
if(f[x]!=x){
int l=f[x];
f[x]=find(f[x]);
d[x]+=d[l];
}
return f[x];
}
inline void sakura(int a,int b){
int aa=find(a);int bb=find(b);
if(aa!=bb){
f[aa]=bb;
d[a]=d[b]+1;
}
else
minn=min(minn,d[a]+d[b]+1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
sakura(i,x);
}
printf("%d",minn);
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int fa[1001],n,k;
struct sakura{int u,v,next;}sak[4001];
int st[1001],tot=0;
int p[1001],pp[1001];
void add(int x,int y){
tot++;
sak[tot].u=x;
sak[tot].v=y;
sak[tot].next=st[x];
st[x]=tot;
}
int find(int x){
if (fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
void unionn(int r1,int r2){
fa[r1]=r2;
}
void doit(){
int i,j;
for (i=n-1;i>=1;i--){
pp[i]=1;
for (j=st[i];j;j=sak[j].next){
if (pp[sak[j].v]){
int r1=find(sak[j].u);
int r2=find(sak[j].v);
if (r1!=r2){
unionn(r1,r2);
p[r1]+=p[r2];
p[r2]=p[r1];
}
}
}
if (p[find(i)]>(n+1)/2){
printf("%d",i);
}
}
}
int main(){
scanf("%d",&n);
pp[n]=1;
for (int i=1;i<=n;i++){
scanf("%d",&k);
fa[i]=i;
p[i]=1;
for (int j=1;j<=k;j++){
int x;
scanf("%d",&x);
add(i,x);
}
}
doit();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct T{int x,y;}f[210][210];
int x,y,n,m;char c;T a1,a2;
T s(int x,int y){
while((x==f[x][y].x)&&(y==f[x][y].y))return f[x][y];
return s(f[x][y].x,f[x][y].y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j].x=i,f[i][j].y=j;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>c;
if(c=='D')a1=s(x,y),a2=s(x+1,y);
else a1=s(x,y),a2=s(x,y+1);
if(a1.x==a2.x&&a1.y==a2.y){
printf("%d\n",i);return 0;
}
else f[a2.x][a2.y]=a1;
}
printf("draw");
return 0;
}
/*
����
| |
| |
| |
������ ������
| ����ACʮ�ּ� |
������ ������
| |
| |
| |
����
*/
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
int n,m,k,f[40001],sum;
struct sakura{
int p,a,b,val;
}sak[40001];
inline int find(int x){return f[x]==x?x:find(f[x]);}
inline bool cmp(const sakura &a,const sakura &b){return a.val<b.val;}
inline bool unions(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return 0;
else f[fy]=fx;
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&sak[i].a,&sak[i].b,&sak[i].val);
std::sort(sak+1,sak+1+m,cmp);
for(int i=1;i<=m;i++){
if(unions(sak[i].a,sak[i].b)){
k++;
sum=sak[i].val;
}
if(k==n-1) break;
}
printf("%d %d",n-1,sum);
return 0;
}
#include<algorithm>
#include<cstdlib>
#include<cstdio>
int g,i,j,n,m,p,x,y,c,ans,k,f[2010];
struct QAQ{int l,r,w;}a[40010];
inline int fi(int x){if(x!=f[x])f[x]=fi(f[x]);return f[x];}
inline int cmp(const QAQ &a,const QAQ &b){return a.w<b.w;}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++){
scanf("%d%d%d%d",&p,&x,&y,&c);
if(p==1){ans+=c,f[fi(y)]=fi(x);}
else a[++g].l=x,a[g].r=y,a[g].w=c;
}
std::sort(a+1,a+g+1,cmp);
for(i=1;i<=g;i++){
x=fi(a[i].l),y=fi(a[i].r);
if(x!=y){
f[y]=x;k++;
ans+=a[i].w;
}
}
printf("%d",ans);
return 0;
}