AC日记——封锁阳光大学洛谷 P1330-白红宇

AC日记——封锁阳光大学洛谷 P1330

阅读量：5926 次

发布时间：2019-06-19

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

思路：

　　bfs染色；

　　如果当前点能通往已染色的点则不能完成；

　　图不一定联通；

来，上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define maxn 10005#define maxm 200005struct EdgeType {    int v,e;};struct EdgeType edge[maxm];int n,m,cnt,head[maxn],dis[maxn],ans;bool if_[maxn],ifo;inline void in(int &now){    register int if_z=1;now=0;    register char Cget=getchar();    while(Cget>'9'||Cget<'0')    {        if(Cget=='-') if_z=-1;        Cget=getchar();    }    while(Cget>='0'&&Cget<='9')    {        now=now*10+Cget-'0';        Cget=getchar();    }    now*=if_z;}int main(){    in(n),in(m);int u,v;    for(int i=1;i<=m;i++)    {        in(u),in(v);        edge[++cnt].v=v,edge[cnt].e=head[u],head[u]=cnt;        edge[++cnt].v=u,edge[cnt].e=head[v],head[v]=cnt;    }    for(int i=1;i<=n;i++)    {        if(!if_[i])        {            int tot=1,pos=1;            queue
          
           que;que.push(i),if_[i]=true; while(!que.empty()) { int now=que.front();que.pop(); for(int i=head[now];i;i=edge[i].e) { if(!if_[edge[i].v]) { tot++; que.push(edge[i].v); if_[edge[i].v]=true; dis[edge[i].v]=dis[now]^1; if(dis[now]) pos++; } else { if(dis[edge[i].v]==dis[now]) ifo=true; } } } ans+=min(tot-pos,pos); } } if(ifo) cout<<"Impossible"; else cout<