Cod sursa(job #2706227)

Utilizator GligarEsterabadeyan Hadi Gligar Data 14 februarie 2021 12:45:00
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int nmax=100000;

vector <int> g[nmax+1];

int low[nmax+1];

bool u[nmax+1], u2[nmax+1];

int ctc=1;

void dfs(int x){
    u[x]=1;
    for(int i=0;i<int(g[x].size());i++){
        int xn=g[x][i];
        if(low[x]>low[xn]){
            low[x]=low[xn];
            dfs(xn);
        }
        if(u[xn]==0){
            dfs(xn);
        }
    }
}

void dfs2(int x){
    u2[x]=1;
    for(int i=0;i<int(g[x].size());i++){
        int xn=g[x][i];
        if(low[x]>low[xn]){
            low[x]=low[xn];
        }
        if(u2[xn]==0){
            dfs2(xn);
        }
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
        low[x]=x;
    }
    for(int i=1;i<=n;i++){
        if(u[i]==0){
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(u2[i]==0){
            dfs2(i);
        }
    }
/*
    for(int i=1;i<=n;i++){
        fout<<i<<" ";
    }
    fout<<"\n";
    for(int i=1;i<=n;i++){
        fout<<low[i]<<" ";
    }
    fout<<"\n\n";
*/
    int x=low[1];
    for(int i=2;i<=n;i++){
        if(x!=low[i]){
            x=low[i];
            ctc++;
        }
    }
    fout<<ctc<<"\n";
    x=low[1];
    for(int i=1;i<=n;i++){
        if(x!=low[i]){
            x=low[i];
            fout<<"\n";
        }
        fout<<i<<" ";
    }
    return 0;
}