首页 > 代码库 > AC日记——封锁阳光大学 洛谷 P1330

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

封锁阳光大学

 

思路:

  bfs染色;

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

  图不一定联通;

 

来,上代码:

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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<int>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<<ans;    return 0;}

 

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