Cod sursa(job #2565254)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 2 martie 2020 13:03:22
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 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],time;

void dfs(int n1)
{
    disc[n1]=low[n1]=++time;
    stiva.push_back(n1);
    for(vector<int>::iterator it=adj[n1].begin();it!=adj[n1].end();it++)
    {
        int n2=*it;
        if(disc[n2] && !cc[n2])
            low[n1]=min(low[n1],disc[n2]);
        else 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])
        {
            time=0;
            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;
}