CompetitiveProgramming/recursivectg.cpp at main · darksidergod/CompetitiveProgramming · GitHub

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define ll long long int
#define ii pair<int, int>
#define pb push_back
#define f first
#define s second

using namespace std;

#define SIZE 1000001

vector<int> adj[SIZE];
bool vis[SIZE];
ll col[SIZE];
ll sz;
ll colRed;

void dfs(ll r, ll color)
{
	if(vis[r])
		return;

	vis[r]=1;
	colRed+=color;
	col[r]=color;
	sz++;
	for(ll i:adj[r])
		dfs(i, (1+color)%2);

}

int main(void)
{
	int t;
	cin>>t;
	while(t--)
	{
		ll n, m, ans=0;
		bool valid=true;
		cin>>n>>m;
		vector< pair<ll, ll> > edges;
		for(int i=1; i<=n; i++)
			adj[i].clear();

		memset(vis, 0, sizeof(vis));
		memset(col, -1, sizeof(col));

		for(int i=0; i<m; i++)
		{
			ll u, v;
			cin>>u>>v;
			edges.push_back({u,v});
			adj[u].pb(v);
			adj[v].pb(u);
		}

		for(int i=1; i<=n; i++)
		{
			if(!vis[i])
			{
				sz=0;
				colRed=0;
				dfs(i, 0);
				ans+=max(sz-colRed, colRed);
			}
		}

		for(int i=0; i<m; i++)
		{
			pair<ll, ll> p;
			p=edges[i];
			if(col[p.f]==col[p.s])
				valid=false;
		}

		if(!valid)
			cout<<"NO\n";

		else
			cout<<ans<<"\n";
	}

	return 0;
}