[BZOJ]1116: [POI2008]CLO-白红宇

[BZOJ]1116: [POI2008]CLO

阅读量：5058 次

发布时间：2019-06-12

本文共 1705 字，大约阅读时间需要 5 分钟。

题解: 有个显然的结论如果能成环那么必然能让环上的点都满足条件然后与这个环联通的点必然也都能满足要求所以问题转化成对于每个联通块里面边的个数是否都大于点的个数并查集维护即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define link(x) for(edge *j=h[x];j;j=j->next)#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=3e5+10;const double eps=1e-8;#define ll long longusing namespace std;struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}int f[MAXN];int find1(int x){ if(x==f[x])return x; return f[x]=find1(f[x]);}int sz[MAXN],tag[MAXN];int main(){ int n=read();int m=read(); inc(i,1,n)f[i]=i,sz[i]=1; int u,v; inc(i,1,m){ u=read();v=read(); int t1=find1(u);int t2=find1(v); if(t1==t2){tag[t1]++;continue;} f[t1]=t2;sz[t2]+=sz[t1];tag[t2]+=(tag[t1]+1); } inc(i,1,n){ int t1=find1(i); if(tag[t1]>=sz[t1])continue; printf("NIE\n"); return 0; } printf("TAK\n"); return 0;}

1116: [POI2008]CLO

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 1464 Solved: 795

[][][]

Description

Byteotia城市有n个 towns m条双向roads. 每条 road 连接两个不同的 towns ,没有重复的road. 你要把其中一些road变成单向边使得：每个town都有且只有一个入度

Input

第一行输入n m.1 <= n<= 100000,1 <= m <= 200000 下面M行用于描述M条边.

Output

TAK或者NIE 常做POI的同学,应该知道这两个单词的了...

Sample Input

4 5

1 2

2 3

1 3

3 4

1 4

Sample Output

TAK

上图给出了一种连接方式.

转载于:https://www.cnblogs.com/wang9897/p/10343887.html

你可能感兴趣的文章