Cod sursa(job #2565297)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 2 martie 2020 13:30:40
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#define NMAX 100000
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

vector< int > adj[NMAX];
vector< int > stiva;
vector< int > scc[NMAX];
int nrc,disc[NMAX],low[NMAX],cc[NMAX],t;

void dfs(int n1)
{
    disc[n1]=low[n1]=++t;
    stiva.push_back(n1);
    for(vector<int>::iterator it=adj[n1].begin();it!=adj[n1].end();it++)
    {
        int n2=*it;
        if(!cc[n2])
        {
            if(!disc[n2])
                dfs(n2);
            low[n1]=min(low[n1],low[n2]);
        }
    }
    if(disc[n1]==low[n1])
    {
        nrc++;
        while(stiva.back()!=n1)
        {
            scc[nrc].push_back(stiva.back());
            cc[stiva.back()]=nrc;
            stiva.pop_back();
        }
        scc[nrc].push_back(n1);
        cc[n1]=nrc;
        stiva.pop_back();
    }
}

int main()
{
    int n,m,i,j,x,y;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
    }
    for(i=1; i<=n; i++)
    {
        if(!disc[i])
            dfs(i);
    }
    cout<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(vector<int>::iterator it=scc[i].begin();it!=scc[i].end();it++)
            cout<<*it<<' ';
        cout<<'\n';
    }
    return 0;
}