icpc:problems:luogup1330
problems | |
---|---|
名称 | 封锁阳光大学 |
题目编号 | P1330 |
题目链接 | luogu.com.cn/… |
来源 | Luogu |
算法分类 | 图论, DFS, 染色 |
难易程度 | 容易 |
封锁阳光大学
想法
建图、染色、判断。图不是联通图,故需要全部点枚举与遍历。
代码实现
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N = 1e4+10; vector<int>edge[N]; int n, m, vis[N], cnt[2]; bool flag = true; void DFS(int x) { for(int i=0; i<(int)edge[x].size(); i++) { int v = edge[x][i]; if(vis[x] == vis[v]) { flag = false; return ; } if(vis[v] != -1)continue; vis[v] = !vis[x]; cnt[vis[v]]++; DFS(v); } return ; } int main() { int x, y; scanf("%d %d", &n, &m); for(int i=1; i<=m; i++) { scanf("%d %d", &x, &y); edge[x].push_back(y); edge[y].push_back(x); } memset(vis, -1, sizeof(vis)); int ans = 0; for(int i=1; i<=n; i++) { if(vis[i] != -1)continue; cnt[0] = 0; cnt[1] = 1; vis[i] = 1; DFS(i); if(!flag)break; ans += min(cnt[1], cnt[0]); } if(!flag) printf("Impossible"); else printf("%d", ans); return 0; }
/app/www/public/data/pages/icpc/problems/luogup1330.txt · 最后更改: 2024/01/20 11:55 由 温婕莺