Cod sursa(job #2173346)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 15 martie 2018 21:44:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define nmax 100005
ifstream f("ctc.in");
ofstream g("ctc.out");

bool viz[nmax],instk[nmax];
vector<int>Q[nmax];
vector<int>stk,result[nmax];
int n,m,lowest[nmax],niv[nmax],nrcomponente,index;

void read()
{
    f>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int e1,e2;
        f>>e1>>e2;
        Q[e1].push_back(e2);
    }
}

void dfs(int nod)
{
    instk[nod]=true;
    lowest[nod]=niv[nod]=++index;
    stk.push_back(nod);
    for (auto w:Q[nod])
    {
        if (!niv[w])
        {
            dfs(w);
            lowest[nod]=min(lowest[nod],lowest[w]);
        }
        else if (instk[w])
            lowest[nod]=min(lowest[nod],niv[w]);
    }
    if (lowest[nod]==niv[nod])
    {
        while (stk.size()&&lowest[stk.back()]>=lowest[nod])
        {
            result[nrcomponente].push_back(stk.back());
            instk[stk.back()]=false;
            stk.pop_back();
        }
        ++nrcomponente;
    }
}


void solve()
{
    for (int i=1; i<=n; ++i)
        if (!niv[i])
            dfs(i);
    g<<nrcomponente<<'\n';
    for (int i=0;i<nrcomponente;++i)
    {
        for (auto w:result[i])
            g<<w<<' ';
        g<<'\n';
    }
}

int main()
{
    read();
    solve();
    return 0;
}