hihocoder 1176

题意：N,M。分别表示岛屿数量和木桥数量，一笔画

分析：欧拉路问题(给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路)

欧拉路的条件

一个无向图存在欧拉路当且仅当该图是连通
且只有2个点的度数是奇数（此时这两个点只能作为欧拉路径的起点和终点

用并查集判断第一个条件

第二个直接用数组存

 #include <iostream>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <map>

 #include <iomanip>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <set>

 #include <vector>

 //const int maxn = 1e5+5;

 #define ll long long

 #define MAX INT_MAX

 #define FOR(i,a,b) for( int i = a;i <= b;++i)

 using namespace std;

 int fh[],degree[];

 int n,m,cnt1,cnt2,a,b;

 int findhead(int k)  //并查集判断条件一

 {

     if(fh[k]==-)

         return k;

      return fh[k]=findhead(fh[k]);

 }

 int main()

 {

     //    freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);

     //    freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);

     cin>>n>>m;

     memset(fh,-,sizeof(fh));

     for(int i=;i<=m;++i)

     {

         cin>>a>>b;

         degree[a]++;

         degree[b]++;

         a=findhead(a);

         b=findhead(b);

         if(a!=b)

             fh[a]=b;

     }

     for(int i=;i<=n;++i)

     {

         if(findhead(i)==i)

         {

             cnt1++;

         }

         if(degree[i]%==)

         {

             cnt2++;

         }

     }

     //cout<<cnt1<<"   "<<cnt2<<endl;

     if(cnt1==&&(cnt2==||cnt2==))　　//head点只有一个切 度奇数点为2或者0

     {

         cout<<"Full";

     }

     else cout<<"Part";

 }