Submission #976590

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MAXN = 120000;

int was[MAXN];
vector<int> vv;
vector<int> eds[MAXN];
vector<int> reds[MAXN];
int n, m;
int cl[MAXN];

void dfs1(int v) {
	was[v] = 1;
	vv.push_back(v);
	for (int u: eds[v]) {
		if (!was[u])
			dfs1(u);
	}
	for (int u: reds[v]) {
		if (!was[u])
			dfs1(u);
	}
}

int dfs2(int v, int c) {
	cl[v] = c;
	for (int u: eds[v]) {
		if (cl[u] == -1) {
			if (dfs2(u, (c + 1) % 3))
				return 1;
		}
		else {
			if (cl[u] != (c + 1) % 3)
				return 1;
		}
	}
	for (int u: reds[v]) {
		if (cl[u] == -1) {
			if (dfs2(u, (c + 2) % 3))
				return 1;
		}
		else {
			if (cl[u] != (c + 2) % 3)
				return 1;
		}
	}
	return 0;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		eds[a].push_back(b);
		reds[b].push_back(a);
	}
	fill(cl, cl + n, -1);
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		if (was[i])
			continue;
		vv.clear();
		dfs1(i);
		int st = -1;
		for (int u: vv) {
			if (!reds[u].empty() && !eds[u].empty()) {
				st = u;
				break;
			}
		}
		if (st == -1) {
			for (int u: vv)
				ans += eds[u].size();
			continue;
		}
		if (dfs2(st, 0)) {
			ll sz = vv.size();
			ans += sz * sz;
			continue;
		}
		ll cc[3] = {};
		for (int u: vv)
			++cc[cl[u]];
		ans += cc[0] * cc[1] + cc[1] * cc[2] + cc[2] * cc[0];
	}
	cout << ans << "\n";
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:71:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
./Main.cpp:74:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^

Judge Result