Topic Description

Cao is an old Cao who loves to brush the streets. During the summer vacation, he brushes the streets in the campus of Sunshine University happily every day. The river crab was upset to see the cheerful Cao. The crab decided to block Sunshine University from Cao Brug Street.

The campus of Sunshine University is an undirected graph composed of N points, which are connected by M roads. Every crab can block a point. When a point is blocked, the roads connecting it are blocked. Cao can't brush the streets with these roads. The tragic thing is that crabs are a disharmonious creature. When two Crabs block two adjacent points, they will clash.

Question: At least how many crabs are needed to block all roads without conflict.

Input and output format

Line 1: Two integers N, M

Next, line M: Two integers A and B in each line, indicating that there is a road connection between point A and point B.

Only one line: If the crab can't block all roads, output "Impossible" or output an integer to indicate how many crabs are needed at least.

Input and Output Samples

[Input Sample 1]
3 3
1 2
1 3
2 3

[Input Sample 2]
3 2
1 2
2 3

[Output Sample 1]
Impossible

[Output Sample 2]
1

Explain

[Data Scale]

1 < = N < = 10000, 1 < = M < = 100000, there is at most one road between any two points.

Well, it means that Ben Bao doesn't know what black and white dyeing is, so the problem can't be solved.

But I also use BFS+DFS for AC.

Ideas:

Because the points are not necessarily connected.

So we enumerate all points on one side and run DFS for each point that has not been visited.

In the process of DFS, the point connected to the point is accessed at the same time.

Then the DFS is carried out in the process of each DFS.

Calculate the number of components that need to be placed from this point.

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstdlib>
  6 #include<queue>
  7 using namespace std;
  8 void read(int & n)
  9 {
 10     char c='+';int x=0;
 11     while(c<'0'||c>'9')
 12     c=getchar();
 13     while(c>='0'&&c<='9')
 14     {
 15         x=x*10+(c-48);
 16         c=getchar();
 17     }
 18     n=x;
 19 }
 20 const int MAXN=10101;
 21 struct node
 22 {
 23     int u,v,nxt;
 24 }edge[MAXN*10+101];
 25 struct dian
 26 {
 27     int bh;
 28     int how;// 0 No, 1. 
 29 }sz[MAXN];
 30 int n,m;
 31 int head[MAXN];
 32 int vis1[MAXN];
 33 int vis2[MAXN];
 34 int fang[MAXN];// Record whether this point is placed or not 
 35 int num=1;
 36 int ans1=0x7fffff,ans2=0,out=0;
 37 void add_edge(int x,int y)
 38 {
 39     edge[num].u=x;
 40     edge[num].v=y;
 41     edge[num].nxt=head[x];
 42     head[x]=num++;
 43 }
 44 void bfs(int p,int fbf)
 45 {
 46     memset(vis2,0,sizeof(vis2));
 47     dian bg;
 48     bg.bh=p;
 49     bg.how=1;
 50     queue<dian>q;
 51     q.push(bg);
 52     while(q.size()!=0)
 53     {
 54         dian now=q.front();
 55         vis2[now.bh]=now.how;
 56         q.pop();
 57         if(now.how==1)
 58         ans2++;
 59         for(int i=head[now.bh];i!=-1;i=edge[i].nxt)
 60         {
 61             dian will;
 62             will.bh=edge[i].v;
 63             if(now.how==1)will.how=2;
 64             else will.how=1;
 65             if(vis2[edge[i].v])
 66             {
 67                 if(vis2[edge[i].v]==now.how)
 68                 {
 69                     printf("Impossible");
 70                     exit(0);
 71                 }
 72                 else continue;
 73             }
 74            
 75             q.push(will);
 76         }
 77     }
 78     ans1=min(ans1,ans2);
 79 }
 80 void dfs(int p)
 81 {
 82     ans2=0;
 83     vis1[p]=1;
 84     bfs(p,1);
 85     for(int i=head[p];i!=-1;i=edge[i].nxt)
 86     {
 87         if(vis1[edge[i].v]==0)
 88         {
 89             ans2=0;
 90             dfs(edge[i].v);    
 91         }
 92     }
 93 }
 94 int main()
 95 {
 96     read(n);read(m);
 97     for(int i=1;i<=n;i++)
 98     head[i]=-1;
 99     for(int i=1;i<=m;i++)
100     {
101         int x,y;
102         read(x);read(y);
103         add_edge(x,y);
104         add_edge(y,x);
105     }
106     int ans=0;
107     for(int i=1;i<=n;i++)
108     {
109         if(vis1[i]==0&&head[i]!=-1)
110         {
111             ans1=0x7ffff;
112             dfs(i);
113             out+=ans1;
114         }
115         
116     }
117     printf("%d",out);
118     return 0;
119 }