牛客练习赛106 E(二分图捏)

题目
题意: 给定n个点的无向完全图，现在删去m条边，判断图中是否存在长度为奇数的环。
思路: 首先要知道二分图是没有奇数环的图，所以这个题本质是判断是否存在二分图，如果不存在二分图，说明存在长度为奇数的环。而二分图的话，dfs染色即可判断是否存在。
这个题过的时候600多ms，属于卡过的，因为直接染色的话理论复杂度是O(n+m)，m是nn，但是其实枚举不完这么多边就会提前结束了，可以推式子证明。
二分图左部n1个点，右部n2个点。满足:
n1 + n2 = n
n(n-1)/2 - m <= n1n2.
当n1 = n2 = n/2，n1n2最大。
当m<=nn/4 - n/2，有可能存在二分图，若m > nn/4-n/2，不可能存在二分图，说明必有奇环，直接减枝剪掉。因为m最大是2e5，所以n基本大于1000就直接剪掉了。
时间复杂度O(n+m)
PS:这里还跟大佬学了一手，我本来用的map存的删除的边，但是发现可以用二维vector，这样就O(1)了，用map还带log。用二维指针建二维数组也可以，但是指针经常指不明白。
代码:

#include
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int n,m,k,T;
int vis[N];
vector<vector<int> >mp;
bool dfs(int cur,int c)
{
	vis[cur] = c;
	for(int i=1;i<=n;++i)
	{
		if(i==cur) continue;
		int wh = mp[cur][i];
		if(wh==0) continue;
		if(vis[i]==c) return false;
		if(!vis[i]&&!dfs(i,3-c)) return false;
	}
	return true;
}
void solve()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) vis[i] = 0;
    bool flag = 0;
    if(m<1ll*n*n/4-n/2) {printf("YES\n"); return ;}
    mp = vector<vector<int> >(n, vector<int>(n, 1));
	while(m--)
	{
		int x,y; scanf("%d%d",&x,&y);
		x--,y--;
		mp[x][y] = mp[y][x] = 0;
	}
	for(int i=1;i<=n&&!flag;++i)
	{
		if(!vis[i]&&!dfs(i,1)) flag = 1; //不是二分图，有奇数环 
	}
	if(flag) printf("YES");
	else printf("NO");
    printf("\n");
}
signed main(void)
{
// 	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
	cin>>T;
	while(T--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int n,m,k,T;
int vis[N];
int **mp;
bool dfs(int cur,int c)
{
	vis[cur] = c;
	for(int i=1;i<=n;++i)
	{
		if(i==cur) continue;
		int wh = mp[cur][i];
		if(wh==1) continue;
		if(vis[i]==c) return false;
		if(!vis[i]&&!dfs(i,3-c)) return false;
	}
	return true;
}
void solve()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) vis[i] = 0;
    bool flag = 0;
    if(m<1ll*n*n/4-n/2) {printf("YES\n"); return ;}
    mp = new int*[n+1];
    for(int i=1;i<=n;++i)
    {
    	mp[i] = new int[n+1];
	}
	while(m--)
	{
		int x,y; scanf("%d%d",&x,&y);
//		x--,y--;
		mp[x][y] = mp[y][x] = 1;
	}
	for(int i=1;i<=n&&!flag;++i)
	{
		if(!vis[i]&&!dfs(i,1)) flag = 1; //不是二分图，有奇数环 
	}
	if(flag) printf("YES");
	else printf("NO");
    printf("\n");
//     for(int i=1;i<=n;++i) delete[]mp[i];
//     delete[]mp;
}
signed main(void)
{
// 	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
	cin>>T;
	while(T--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56