去西安旅游最佳路线/南京seo关键词排名

Codevs 1535 封锁阳光大学

根据题意将相邻的点染色， 如果在染色过程中碰到下一个点跟自己同色的情况就 不合法；把图染完色后，记录一下每种颜色的数量，取最小值， 如果是森林， 最后的答案是就每一个分图 的 min 相加。

DFS

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;#define MAX_V (10000+10)
#define MAX_E (100000+10)
int V, E, tot = 0;
int first[MAX_V], nxt[MAX_E << 1];
int vis[MAX_V];
struct edge{int from, to;
}es[MAX_E << 1];void build(int ff, int tt)
{es[++tot] = (edge){ff,tt};nxt[tot] = first[ff];first[ff] = tot;
}bool h = 0;
int ans1 = 0, ans2 = 0;
void dfs(int x, int c)
{vis[x] = c;if(c == 1) ans1 ++;else ans2 ++;for(int i = first[x]; i != -1; i = nxt[i]){int v = es[i].to;if(vis[v]){if(vis[v] == c){h = 1;return;}continue;}dfs(v, c%2+1);}
}int main()
{cin >> V >> E;memset(first,-1,sizeof(first));for(int i = 1; i <= E; i ++){int f, t;scanf("%d%d", &f, &t);build(f,t); build(t,f);}int ans = 0;for(int i = 1; i <= V && !h; i ++)if(!vis[i]){ans1 = ans2 = 0;dfs(i,1);ans += min(ans1, ans2);}if(h) puts("Impossible");else printf("%d\n", ans);return 0;
}

BFS

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;#define MAX_V (10000+10)
#define MAX_E (100000+10)
int V, E, tot = 0;
int first[MAX_V], nxt[MAX_E << 1];
int vis[MAX_V];
struct edge{int from, to;
}es[MAX_E << 1];void build(int ff, int tt)
{es[++tot] = (edge){ff,tt};nxt[tot] = first[ff];first[ff] = tot;
}struct ZT{int x, c;
};bool h = 0;
int ans1 = 0, ans2 = 0;
queue <ZT> q;
void bfs(int x, int c)
{q.push((ZT){x,c});vis[x] = c;while(q.size()){ZT x = q.front();q.pop();if(x.c == 1) ans1 ++;else ans2 ++;for(int i = first[x.x]; i != -1; i = nxt[i]){int v = es[i].to;if(vis[v]){if(vis[v] == x.c){h = 1;return;}continue;}vis[v] = x.c%2+1;q.push((ZT){v, x.c%2+1});}}
}int main()
{cin >> V >> E;memset(first,-1,sizeof(first));for(int i = 1; i <= E; i ++){int f, t;scanf("%d%d", &f, &t);build(f,t); build(t,f);}int ans = 0;for(int i = 1; i <= V && !h; i ++)if(!vis[i]){ans1 = ans2 = 0;bfs(i,1);ans += min(ans1, ans2);}if(h) puts("Impossible");else printf("%d\n", ans);return 0;
}