求大佬帮忙改下。。自己改了一天也不会 想法是减去出度。。
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxm 100050
#define maxn 10050
using namespace std;
struct Edge
{
int to;
int next;
} edge[maxm];
struct Cnt
{
int out; //out代表出度 ,此处out只用于排序
int num;
} cnt[maxn];
int m,n,ans,head[maxm],edge_num,hexie[maxn],out[maxn]; //out代表出度
bool cmp(Cnt a,Cnt b)
{
return a.out>b.out;
}
void add(int from,int to) //数组模拟邻接表
{
edge[++edge_num].next=head[from];
edge[edge_num].to=to;
head[from]=edge_num;
}
void blockway(int u) //封锁道路
{
hexie[u]=1;
for(int i=head[u]; i; i=edge[i].next)
{
int v=edge[i].to;
out[v]--;
out[u]--;
}
}
void peace(int u)
{
for(int i=head[u]; i; i=edge[i].next)
{
int v=edge[i].to;
if(hexie[v]==1) return;
}
if(cnt[u].out) ans++;
blockway(u);
}
void cheak()
{
for(int i=1; i<=n; i++)
{
if(out[i])
{
cout<<"Impossible";
return;
}
}
cout<<ans;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cnt[i].num=i;
cnt[i].out=0;
}
for(int i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
cnt[x].out++;
cnt[y].out++;
out[x]++;
out[y]++;
}
sort(cnt+1,cnt+1+n,cmp); //从出度最多的点开始排序
for(int i=1; i<=n; i++)
{
if(out[cnt[i].num]) peace(cnt[i].num);
}
cheak();
return 0;
}