Cod sursa(job #2452261)

Utilizator YetoAdrian Tonica Yeto Data 30 august 2019 11:10:46
Problema Componente tare conexe Scor 12
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, i, j, t, s, sol;
int x, y, numSCC;
int v[100001];
int f[100001], leader[100001];
int a[100001][50], b[100001][50];
bool exp[100001];
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

void DFS(int i)
{
    exp[i]=1;
    for (int cnt=1;cnt<=b[i][0];cnt++) {
        if (exp[ b[i][cnt] ]==0) {
            DFS(b[i][cnt]);
        }
    }
    t++;
    f[i]=t;
}

void DFSSCC(int i)
{
    exp[i]=1;
    leader[i]=s;
    for (int cnt=1;cnt<=a[i][0];cnt++) {
        if (exp[ a[i][cnt] ]==0) {
            DFSSCC(a[i][cnt]);
        }
    }
}

int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        a[x][++a[x][0]]=y;
        b[y][++b[y][0]]=x;
    }

    t=0;
    for (i=n;i>=1;i--) {
        if (exp[i]==0) {
            DFS(i);
        }
    }

    for (i=1;i<=n;i++) {
        v[f[i]]=i;
    }

    memset(exp, 0, sizeof(exp));
    s=NULL;
    for (i=n;i>=1;i--) {
        if (exp[v[i]]==0) {
            s=v[i];
            DFSSCC(v[i]);
        }
    }

    memset (f, 0, sizeof(f));
    for (i=1;i<=n;i++) {
        if (f[leader[i]]==0)
            sol++;
        f[leader[i]]++;
    }

    fout<<sol<<"\n";
    /*
    fout<<f[n]<<","<<f[n-1]<<","<<f[n-2]<<","<<f[n-3]<<","<<f[n-4];
    for (i=1;i<=n;i++) {
        fout<<leader[i]<<" ";
    }*/
    return 0;
}