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;
}

Download