Submission #1791925

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define	MOD  1000000007;
#define PI = 3.14159265358979323846;
using namespace std;

static const int N = 51;
static const int MAX = 100000;
static const int NIL = -1;
static const int INF = (1 << 21);

int n;
vector<int> G[N];
int color[N];

void dfs(int r, int c)
{
	stack<int> S;
	S.push(r);
	color[r] = c;

	while (!S.empty())
	{
		int u = S.top();
		S.pop();

		for (int i = 0; i < G[u].size(); i++)
		{
			int v = G[u][i];

			if (color[v] == NIL)
			{
				color[v] = c;
				S.push(v);
			}
		}
	}
}

void assignColor()
{
	int id = 1;

	for (int i = 1; i <= n; i++)
	{
		color[i] = NIL;
	}

	for (int u = 1; u <= n; u++)
	{
		if (color[u] == NIL) {
			dfs(u, id++);
		}
	}
}

int main()
{
	//Input
	int m;
	cin >> n >> m;

	int S[51];
	int T[51];

	for (int i = 0; i < m; i++)
	{
		cin >> S[i] >> T[i];
	}

	int count = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			G[S[j]].clear();
			G[T[j]].clear();
		}

		for (int j = 0; j < m; j++)
		{
			if (j != i)
			{
				G[S[j]].push_back(T[j]);
				G[T[j]].push_back(S[j]);
			}
		}

		assignColor();

		for (int j = 0; j < m; j++)
		{
			if (color[S[j]] != color[T[j]])
			{
				count++;
			}
		}
	}

	cout << count << endl;
	return 0;
}

Submission Info

Judge Result