求大佬改bug
查看原帖
求大佬改bug
92591
DCrystal楼主2018/6/14 18:14

求大佬帮忙改下。。自己改了一天也不会 想法是减去出度。。

#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;
}
2018/6/14 18:14
加载中...