dfs 判断二分图 && dsu判断图的连通性

最新推荐文章于 2022-12-20 20:41:17 发布

开学了8

最新推荐文章于 2022-12-20 20:41:17 发布

阅读量398

点赞数

文章标签：深度优先算法

本文链接：https://blog.csdn.net/luker6/article/details/122496192

版权

二分图专栏收录该内容

1 篇文章

订阅专栏

HDU-3478
题目大意：
给一个起点，判断是否存在一个某个时刻，能到达所有点？
（1）判断图是不是连通的
（2）如果是二分图，那么图会被分为两个部分，不能到达

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int fa[N], color[N];
std::vector<int> G[N];

int find(int x)
{
	if(fa[x] == x) return fa[x];
	return fa[x] = find(fa[x]);
}

void Union(int x, int y)
{
	fa[find(x)] = find(y);
}

bool dfs(int x)
{
	for(int i = 0; i < (int)G[x].size(); i++) {
		int y = G[x][i];
		if(color[x]==color[y]){
			 return false;
			 
		}
		if(color[y]==0) {
			color[y] = 3 - color[x];
			if(!dfs(y)) {
				return false; 
				
			}
		}
	}
	return true;
}

int main()
{
	int t;
	scanf("%d", &t);
	for(int Case = 1; Case <= t; Case++)
	{
		int n, m, s;
		scanf("%d %d %d", &n, &m, &s);
		memset(color, 0, sizeof color);
		for(int i = 0; i < n; i++) {
			G[i].clear();
			fa[i] = i;
		}
		while(m--)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
			Union(x, y);
		}
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			if(fa[i] == i) {
				cnt ++;
			}
		}
		if(cnt>1) { // 连通块超过一个
			printf("Case %d: No\n", Case);
		}
		else{
			color[s] = 1;
			if(!dfs(s))  printf("Case %d: YES\n", Case);
			else printf("Case %d: NO\n", Case);
		}
	}
	return 0;
}