记录编号	121065	评测结果	AAAAAAAAAA
题目名称	线段	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-09-17 22:01:47	内存使用	0.62 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct data
{
  int a,b,k;
  data (int a,int b,int k):a(a),b(b),k(k){};
};
//==============var declaration=================
const int MAXN=310;
int root[MAXN],relation[MAXN],temp[MAXN][MAXN];
vector <data> R;
int n,m,t;
bool Error;
//==============function declaration============
int findr(int x);
void cross(int a,int b,int k);
//==============main code=======================
int main()
{  
  string FileName="line";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
  clock_t Start_Time=clock();
#endif    
  scanf("%d",&t);
  while (t--)
  {
    int a,b,k;
    R.clear();
    scanf("%d%d",&n,&m);
    Error=false;
    For(i,1,n)
    {
      root[i]=i;
      relation[i]=0;
    }
    memset(temp,-1,sizeof(temp));
    For(i,1,m)
    {
      scanf("%d%d%d",&a,&b,&k);
      if (a>b)
        a^=b^=a^=b;
      temp[a][b]=k;
    }
    m=-1;
    For(i,1,n)
      For(j,1,n)
        if (temp[i][j]!=-1)
        {
          R.push_back(data(i,j,temp[i][j]));
          m++;
        }
    For(i,0,m)
    {
      a=R[i].a;b=R[i].b;k=R[i].k;
      if (findr(a)!=findr(b))
        cross(a,b,k);
      else
      {
        int ra=relation[a];
        int rb=relation[b];
        if ((ra+rb)%2!=k)
        {
          Error=true;
          break;
        }
      }
    }
    if (Error)
      printf("No Answer\n");
    else if (findr(1)!=findr(n))
      pritnf("2\n");
    else
      printf("%d\n",(relation[1]+relation[n])%2);
  }
#ifdef DEBUG  
  clock_t End_Time=clock();
  cout<<endl<<endl<<"Time Used: "<<(End_Time-Start_Time)/CLOCKS_PER_SEC<<endl;
#endif    
  return 0;
}
//================fuction code====================
int findr(int x)
{
  if (root[x]==x)
    return x;
  int pa=findr(root[x]);
  relation[x]=(relation[x]+relation[root[x]])%2;
  root[x]=pa;
  return pa;
}
void cross(int a,int b,int k)
{
  int ra=findr(a);
  root[ra]=b;
  relation[ra]=(k+relation[a])%2;
}