Bicikli

#include <bits/stdc++.h>
using namespace std;
#define MAXN 10100
vector<int> v[MAXN], rev[MAXN], loops;
int p[MAXN], reachable[MAXN];
void create_topo(int s)
{
	if (p[s] == 1) {
		loops.push_back(s);
		return;
	}
	if (p[s] == 2) return;
	p[s] = 1;
	for (int u : v[s]) {
		create_topo(u);
	}
	p[s] = 2;
}
void reverse_trav(int s)
{
	if (reachable[s]) return;
	reachable[s] = 1;
	for (int u : rev[s]) {
		reverse_trav(u);
	}
}
const long mod = (long) 1e11;
int pad = 0;
int visited[MAXN];
long res[MAXN];
long calc(int s)
{
	if (s == 0) return 1;
	if (visited[s]) return res[s];
	visited[s] = 1;
	long o = 0;
	for (int u : rev[s]) {
		o += calc(u);
		if (o >= mod) pad = 1;
		o %= mod;
	}
	return res[s] = (o % mod);
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		v[a].push_back(b);
		rev[b].push_back(a);
	}
	int ok = 1;
	create_topo(0);
	reverse_trav(1);
	for (int u : loops) {
		if (reachable[u]) {
			ok = 0;
		}
	}
	if (!ok) {
		cout << "inf\n";
		return 0;
	}
	long z = calc(1);
	if (z > (long) 1e9) pad = 1;
	z %= (long) 1e9;
	string b = to_string(z);
	if (pad && b.size() != 9) b = string(9 - b.size(), '0') + b;
	cout << b << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED