#include <stdio.h>
#define maxn 50004

int  parent[maxn];
int    relation[maxn];   
 int result[][3]={1 , -1 , 0, 0 , 1 , -1 , -1 , 0 , 1};
 int result2[][3]={0 , 1 , -1 , -1 , 0 , 1 , 1 , -1 , 0};
 int next[][3]={1 , -1 , 0 , -1 , 0 , 1 , 0 , 1 , -1};
 int behind[][3]={0 , -1 , 1 , 1 , 0 , -1 , -1 , 1 , 0};

 void find(int x,int &y,int &d)
 {
    int z,r,now;
	d=0;z=x;
	 while (parent[x] > 0)
	 { d = next[d+1][relation[x]+1];
        x = parent[x];
     }
	 y = x; now = d;

	  while (z !=y )
	 { 
		  x = parent[z];
        parent[z] = y;
        r = relation[z];
        relation[z] = now;
        now = behind[now+1][r+1];
        z = x;
     } 
 }

 void merge(int a,int b,int r)
 {
   if(parent[a]>parent[b])
     {
	    parent[b] = parent[a] + parent[b];
        parent[a] = b;
        relation[a] = r;
     }
   else {
          parent[a] = parent[a] + parent[b];
        parent[b] = a;
        relation[b] = -r;
        }
 
 }

int main()
{
	 int n , k , lie , i ;    
     int x , y , a , b   ;  
     int u , v , d , nr  ;
	scanf("%d%d",&n,&k);

	for(i=1;i<=n;i++)
	{
	   parent[i] = -1;
      relation[i] = 0;
	}

	lie=0;
	for(i=1;i<=k;i++)
	{
	  scanf("%d%d%d",&d,&x,&y);
	  if(x>n||y>n)
		{
	      lie+=1;
		  continue;
	    }
       find(x , a , u);
       find(y , b , v);
	   if(d==2)  nr = result[u+1][v+1];
	   else  nr = result2[u+1][v+1];
          if(a==b)
		{
		  if(nr!=0) 
			  lie+=1;
		}

		else   merge(a , b , nr);
 
	}

	  printf("%d\n",lie);	
	return 0;
}

• 又一个拿自己的代码出来炫的 (1749) frkstyc 2006-03-04 20:17:44
  • frkstyc 大牛教训的是 (26) fxzy 2006-03-04 20:21:33
    • 请不要把某种动物的名称接在我的id后面 (30) frkstyc 2006-03-04 20:24:46
      • frkstyc大哥教训的对.... (65) fxzy 2006-03-04 20:30:32
        • Re: frkstyc大哥教训的对.... (113) frkstyc 2006-03-04 20:33:23
  • FXZY大牛被BS了吧！！ (0) Sempr 2006-03-06 11:07:08
  • Re:又一个炫耀自己会打字的 (0) ildg 2006-07-17 13:00:56
• 不好看 (13) Last 2006-03-04 20:37:37
  • 估计是devcpp制造 (17) frkstyc 2006-03-04 20:46:12
    • 和 dev cpp 没关系吧，我的就很好 (0) sunmoonstar 2006-03-06 11:38:06
• 写成class，看着多爽 (1749) wywcgs 2006-03-04 20:55:14
• 很乱，很难看 (1749) sunmoonstar 2006-03-06 11:36:28
  • 算是不错的了 (0) frkstyc 2006-03-06 12:15:16
  • 难道跟长相有关? o_o (0) is2easy 2006-03-06 12:36:22
    • 这个id是不是跟我的有点像？-_-b (0) o_oXo_o 2006-03-06 13:34:26
      • WA,的确很像,好像还有一个和你的一模一样的.真D (0) ecjtunh 2006-07-17 14:34:59
• Re:我的c代码 (不带注释) (12) liuhui110 2006-07-22 09:54:20
• 可以小小的改动一下 (2007) Catalyst 2007-12-29 19:24:57