Cod sursa(job #2760186)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 23 iunie 2021 17:24:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define nmax (int)1e5+1
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");


vector<int> dfs;
vector<int> adj[nmax];
vector<int> adjRev[nmax];
vector<bool> visited(nmax);
vector<int> ans[nmax];

void runDfsRev(int nod)
{
    if(visited[nod]) return;
    visited[nod]=1;
    for(auto next:adjRev[nod])
    {
        runDfsRev(next);
    }
    dfs.push_back(nod);
}

void runDfs(int nod,vector<int> *ans)
{
    if(visited[nod]) return;
    visited[nod]=1;
    for(auto next:adj[nod])
    {
        runDfs(next,ans);
    }
    ans->push_back(nod);
}
int main()
{
    int n,m,k=0;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        f>>a>>b;
        adj[a].push_back(b);
        adjRev[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(!visited[i]) runDfsRev(i);
    }

    //for(auto e:dfs) cout<<e<<' ';


    for(int i=1;i<=n;i++) visited[i]=0;
    for(int i=dfs.size()-1;i>=0;i--)
    {
        if(!visited[dfs[i]])
        {
            k++;
            runDfs(dfs[i],&ans[k]);
        }
    }
    g<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        for(auto e:ans[i])
        {
            g<<e<<' ';
        }
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}