MESSAGE - Truyền tin
Tác giả: RR
Ngôn ngữ: C++
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <memory.h>
#include <sstream>
#include <complex>
#include <iomanip>
#define REP(i,n) for(int i = 0, _n = (n); i < _n; i++)
#define REPD(i,n) for(int i = (n) - 1; i >= 0; i--)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define FOREACH(it,c) for (__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define RESET(c,x) memset (c, x, sizeof (c))
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (c).size()
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define PR(a,n) {cerr<<#a<<" = "; FOR(_,1,n) cerr << a[_] << ' '; cerr <<endl;}
#define PR0(a,n) {cerr<<#a<<" = ";REP(_,n) cerr << a[_] << ' '; cerr << endl;}
using namespace std;
const double PI = 2.0 * acos (0.0);
typedef long long LL;
typedef pair <int, int> PII;
template <class T> inline T MAX (T a, T b) { if (a > b) return a; return b; }
template <class T> inline T MIN (T a, T b) { if (a < b) return a; return b; }
// ptrrsn_1's template
const int MAXV = 1011;
int dfs_num[MAXV + 5], dfs_low[MAXV + 5], visited[MAXV + 5];
int dfsNumberCounter, numSCC;
int V;
vector <int> S;
vector <int> G[MAXV + 5];
vector <int> ls[MAXV + 5];
int reg[MAXV + 5];
bool vao[MAXV + 5];
void tarjanSCC(int u) {
dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
S.PB(u);
visited[u] = 1;
REP (j, SIZE(G[u])) {
int v = G[u][j];
if (dfs_num[v] == -1) tarjanSCC(v);
if (visited[v]) dfs_low[u] = min(dfs_low[u], dfs_low[v]);
}
if (dfs_low[u] == dfs_num[u]) {
++numSCC;
while (1) {
int v = S.back(); S.pop_back(); visited[v] = 0;
ls[numSCC].PB(v);
reg[v] = numSCC;
if (u == v) break;
}
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
scanf("%d", &V);
int m; scanf("%d", &m);
while (m--) {
int u, v; scanf("%d%d", &u, &v);
--u; --v;
G[u].PB(v);
}
RESET(dfs_num, -1); RESET(dfs_low, 0); RESET(visited, 0);
dfsNumberCounter = numSCC = 0;
REP (i, V) if (dfs_num[i] == -1) tarjanSCC(i);
REP(u,V)
REP(i,G[u].size()) {
int v = G[u][i];
if (reg[u] != reg[v]) vao[reg[v]] = true;
}
int res = 0;
FOR(i,1,numSCC) if (!vao[i]) ++res;
printf("%d\n", res);
return 0;
}