Cod sursa(job #2929476)

Utilizator Emma19Tiu Ema Emma19 Data 25 octombrie 2022 22:56:25
Problema Componente tare conexe Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> G[100002];
vector <int> H[100002];
int n , m , x , y , S[100001] , D[100001] , c;
ifstream f("ctc.in");
ofstream g("ctc.out");
void dfs_succ(int v , int c)
{
    S[v] = c;
    for(int i : G[v])
        if(!S[i]) dfs_succ(i , c);
}//in S retin succesorii fiecarui nod

void dfs_pred(int v , int c)
{
    D[v] = c;
    for(int i : H[v])
        if(!D[i]) dfs_pred(i , c);
}//in D retin predecesorii fiecarui nod

int main()
{
    f >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        f >> x >> y;
        G[x].push_back(y);
        H[y].push_back(x);
    }//

    for(int i = 1 ; i <= n ; i++)
        if(!S[i])
        {
            c++;
            dfs_succ(i , c);
            dfs_pred(i , c);
            for(int i = 1 ; i <= n ; i++)
                if(S[i] != D[i]) S[i] = D[i] = 0;
        }

    g << c;

}