poj 1733种类并查集+离散化

xiaoxiao2021-02-28  90

分析:http://blog.csdn.net/xiaoxiaoluo/article/details/7401172#

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define maxn 100005 int n; int m; struct node { int u,v; int x; }; node d[maxn]; int num[maxn]; int cnt; int r[maxn]; int fa[maxn]; int Bin(int x) { int low=0,high=cnt-1,mid; while(low<=high) { mid=(low+high)/2; if(num[mid]==x) return mid; if(num[mid]<x) low=mid+1; else high=mid-1; } return -1; } int find(int x) { if(x!=fa[x]) { int f=fa[x]; fa[x]=find(fa[x]); r[x]=r[x]^r[f]; } return fa[x]; } int main() { cin >> n >> m; for(int i = 0 ; i < maxn ; ++i) fa[i] = i; memset( r,0,sizeof(r) ); for(int i = 0 ; i < m ; ++i) { char str[10]; scanf("%d %d %s",&d[i].u,&d[i].v,str); d[i].u--; if( str[0] == 'o' ) d[i].x = 1; else d[i].x = 0; num[cnt++] = d[i].u, num[cnt++] = d[i].v; } sort(num,num+cnt); cnt=unique(num,num+cnt)-num; // for(int i =0;i < cnt ; ++i)printf("%d ",num[i]); printf("\n"); int i; for( i = 0 ; i < m ; ++i) { int u = Bin( d[i].u ); int v = Bin( d[i].v ); int x = find(u); int y = find(v); // printf("%d %d %d %d\n",u,v,x,y); if( x == y ) { if( r[u] == r[v] && d[i].x == 1 )break; if( r[u] != r[v] && d[i].x == 0 )break; } else { if(d[i].x==1) { fa[x]=y; r[x]=r[u]^r[v]^1; } else { fa[x]=y; r[x]=r[u]^r[v]; } } } printf("%d\n",i); }

转载请注明原文地址: https://www.6miu.com/read-57898.html

最新回复(0)