poj2513(无向图判欧拉路)

链接：

题意：一堆木棍左右两端涂有颜色,同样颜色的能够连接在一起，问全部木棍是否能都连上

代码：

#include <map>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

using namespace std;

char s1[15],s2[15];

map<string,int> mp;

vector<int> G[500005];

int id=1,vis[500005],deg[500005];

void dfs(int S,int &op){

    int i,u;

    op++,vis[S]=1;

    for(i=0;i<G[S].size();i++){

        u=G[S][i];

        if(vis[u])

        continue;

        dfs(u,op);

    }

}

int main(){

    int i,j,u,v,op;

    while(scanf("%s%s",s1,s2)!=EOF){

        if(mp[s1]==0)

        mp[s1]=id++;

        if(mp[s2]==0)

        mp[s2]=id++;

        u=mp[s1],v=mp[s2];

        G[u].push_back(v);

        G[v].push_back(u);

        deg[u]++,deg[v]++;

    }

    if(id==1){

        puts("Possible");

        return 0;

    }

    op=0;

    dfs(1,op);                                  //推断有没有孤立点

    if(op!=id-1){

        puts("Impossible");

        return 0;

    }

    op=0;

    for(i=1;i<id;i++)                           //无向图有0个或两个奇度点含有

    if(deg[i]%2)                                //欧拉回路或欧拉通路

    op++;

    if(op==0||op==2)                            //好像有点卡常，交c++冲过去了...

    puts("Possible");

    else

    puts("Impossible");

    return 0;

}