Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

并查集f[y]=x AC,f[x]=y WA,wa的莫名其妙,那个大佬能解释下?

Posted by swust5120171204 at 2019-03-23 20:55:01 on Problem 1386
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const double pi=acos(-1.0);
const double E=2.718281828459;
using namespace std;
const int N=27;
char s[1100];
int in[N],out[N];
int f[N],vis[N];
void init()
{
    memset(vis,0,sizeof(vis));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    for(int i=0;i<=N;i++)
        f[i]=i;
}
int find(int x)
{
    if(x==f[x]) return f[x];
    else return f[x]=find(f[x]);
}
void unionn(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        f[y]=x;
}
int main()
{
    int T,t;
    int x,y;
    cin>>T;
    while(T--)
    {
        init();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%s",s);
            int len=strlen(s);
            x=s[0]-'a';
            y=s[len-1]-'a';
            out[x]++,in[y]++;
            vis[x]=1,vis[y]=1;
            unionn(x,y);
        }
        int a=0,b=0,cnt=0,falg=0,mark=0;
        for(int i=0;i<26;i++)
        {
            if(vis[i])
            {
                if(f[i]==i)
                    cnt++;
                if(in[i]!=out[i])
                {
                    if(in[i]-out[i]==1)
                        a++;
                    else if(out[i]-in[i]==1)
                        b++;
                    else
                        mark++;
                }
                if(cnt>1||mark)
                {
                    falg=1;
                    break;
                }
            }
        }
        if(falg||mark)
            printf("The door cannot be opened.\n");
        else
        {
            if((a==1&&b==1)||(a==0&&b==0))
                printf("Ordering is possible.\n");
            else
                printf("The door cannot be opened.\n");
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator