poj2513

링크:클릭하여 링크 열기
제목: 나무 막대기 한 무더기의 좌우 양쪽 끝에 색을 칠하여 같은 색깔로 연결할 수 있습니다. 모든 나무 막대기를 연결할 수 있는지 묻습니다. EOF 마감
코드:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node{
    char str[20];
}s[550005],stemp[550005];
char a[20],b[20],temp[550005][20];
int fa[550005],sum[550005];
int cmp(struct node a,struct node b){
    return strcmp(a.str,b.str)<0;
}
int binsearch(char *s,int n){
    int low,high,mid;
    low=0;high=n-1;
    while(low<=high){
        mid=(low+high)/2;
        if(strcmp(temp[mid],s)==0)
        return mid;
        else if(strcmp(temp[mid],s)>0)
        high=mid-1;
        else if(strcmp(temp[mid],s)<0)
        low=mid+1;
    }
}                                           //    
int found(int x){
    if(x!=fa[x])
    fa[x]=found(fa[x]);
    return fa[x];
}
int main(){                                 //               
    int i,j,k,p,xx,yy,flag;                 //               
    i=k=0;                                  //        
    while(scanf("%s%s",a,b)!=EOF){
        strcpy(s[i++].str,a);
        strcpy(stemp[i-1].str,a);
        strcpy(s[i++].str,b);
        strcpy(stemp[i-1].str,b);
        k++;
    }
    sort(s,s+i,cmp);
    strcpy(temp[0],s[0].str);
    p=1;
    for(j=1;j<i;j++)
    if(strcmp(s[j].str,s[j-1].str)!=0)
    strcpy(temp[p++],s[j].str);
//    for(j=0;j<p;j++)
//    cout<<temp[j]<<endl;
    for(j=0;j<p;j++)
    fa[j]=j;
    for(j=0;j<i;j+=2){
        xx=binsearch(stemp[j].str,p);
        yy=binsearch(stemp[j+1].str,p);
//        cout<<stemp[j].str<<" "<<stemp[j+1].str<<endl;
//    cout<<xx<<" "<<yy<<endl;
        sum[xx]++;sum[yy]++;
        if(found(fa[xx])!=found(fa[yy]))    //         
        fa[found(fa[xx])]=found(fa[yy]);
    }
    flag=0;
    for(i=0;i<p;i++)
    if(fa[i]==i)
    flag++;
    if(flag>1){                             //        
        printf("Impossible
");
        return 0;
    }
    flag=0;
    for(i=0;i<p;i++)
    if(sum[i]%2!=0)
    flag++;
    if(flag==2||flag==0)
    printf("Possible
");
    else
    printf("Impossible
");
    return 0;
}