Submission #1784451

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;
const int MaxM = 100000;

int n, m;

struct halfEdge
{
	int v, w;
	halfEdge *next;
};
halfEdge adj_pool[MaxM * 2], *adj_tail = adj_pool;
halfEdge *adj[MaxN + 1];

inline void addEdge(const int &u, const int &v, const int &w)
{
	adj_tail->v = v, adj_tail->w = w;
	adj_tail->next = adj[u], adj[u] = adj_tail++;
}

int num[4];
bool inv;

int col[MaxN + 1];

void dfs(const int &u, const int &now)
{
	col[u] = now;
	++num[col[u]], ++num[3];

	for (halfEdge *e = adj[u]; e; e = e->next)
	{
		int l = (now + e->w) % 3;
		if (!~col[e->v])
			dfs(e->v, l);
		else if (col[e->v] != l)
			inv = true;
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int u = getint(), v = getint();
		addEdge(u, v, 1);
		addEdge(v, u, 2);
	}

	for (int u = 1; u <= n; ++u)
		col[u] = -1;

	s64 res = 0;
	for (int u = 1; u <= n; ++u)
		if (!~col[u])
		{
			inv = false;
			num[0] = num[1] = 0;
			num[2] = num[3] = 0;

			dfs(u, 0);

			if (inv)
				res += (s64)num[3] * num[3];
			else if (!num[0] || !num[1] || !num[2])
				res += num[3] - 1;
			else
			{
				res += (s64)num[0] * num[1];
				res += (s64)num[1] * num[2];
				res += (s64)num[2] * num[0];
			}
		}

	cout << res << endl;

	return 0;
}

Submission Info

Judge Result