Cod sursa(job #3265065)

Utilizator ursus161Stefan Ghetu ursus161 Data 26 decembrie 2024 18:44:41
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define nmax 100

using namespace std;
vector <int> G[nmax]; vector <int> GT[nmax];
int n,m,viz1[nmax],viz2[nmax]; int ctc[nmax]; int nrc;
void dfs1(int nod){
viz1[nod]=1;
for(unsigned int i=1;i<=G[nod].size();i++)
    if(!viz1[G[nod][i]]) dfs1(i);
}
void dfs2(int nod){
viz2[nod]=1;
for(unsigned int i=1;i<=GT[nod].size();i++)
    if(!viz2[GT[nod][i]]) dfs2(i);
}
int main()
{ cin>>n>>m;
    for(int i=1;i<=m;i++){ int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(y);
    }
    for(int i=1;i<=n;i++){
        if(ctc[i]==0){

             for(int j = 1; j <= n ; ++j)
                viz1[j] = viz2[j] = 0;
            nrc ++;
            dfs1(i); dfs2(i);
            for(int j = 1; j <= n ; ++j)
                if(viz1[j] == 1 && viz2[j] == 1)
                    ctc[j] = nrc;
        }
    }
    cout<<nrc;
    return 0;
}