Cod sursa(job #2352632)

Utilizator andrei13Paval Andrei andrei13 Data 23 februarie 2019 14:52:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>

using namespace std;

const int nmax=100010;

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

list <int> adj[nmax];
list <int> componente[nmax];
int n,m;
int disc[nmax],low[nmax];
int nrcomp,timp;
stack <int> stiva;
bool instiva[nmax];

void dfs(int u)
{
    disc[u]=++timp;
    low[u]=timp;
    stiva.push(u);
    instiva[u]=true;
    list <int> :: iterator i;
    for(i=adj[u].begin();i!=adj[u].end();++i)
    {
        int v=*i;
        if(!disc[v])
        {
            dfs(v);
            low[u]=min(low[v],low[u]);
        }
        else
        if(instiva[v])
            low[u]=min(low[u],low[v]);
    }
    if(disc[u]==low[u])
    {
        int w;
        nrcomp++;
        while(stiva.top()!=u)
        {
            w=stiva.top();
            instiva[w]=false;
            componente[nrcomp].push_back(w);
            stiva.pop();
        }
        instiva[u]=false;
        stiva.pop();
        componente[nrcomp].push_back(u);
    }
}

void ctc()
{
    for(int i=1;i<=n;++i)
        if(!disc[i])
           dfs(i);
    g<<nrcomp<<'\n';
    for(int i=1;i<=nrcomp;++i)
    {
        list <int> :: iterator it;
        for(it=componente[i].begin();it!=componente[i].end();++it)
            g<<*it<<' ';
        g<<'\n';
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        adj[x].push_back(y);
    }
    ctc();
    return 0;
}