Cod sursa(job #1690808)

Utilizator TibixbAndrei Tiberiu Tibixb Data 15 aprilie 2016 20:41:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
vector<int> L[100005], st[100005];
stack<int> s;
bool is[100005];
int n, m, i, x, y, niv[100005], low[100005], nod, nrst, lvl, j;
void scc(int nod)
{
    nrst++;
    do
    {
        x=s.top();
        st[nrst].push_back(x);
        s.pop();
        is[x]=0;
    }
    while(x!=nod);
}
void dfsst(int nod)
{
    s.push(nod);
    is[nod]=1;
    niv[nod]=low[nod]=++lvl;
    for(int i=0; i<L[nod].size(); i++)
    {
        int fiu=L[nod][i];
        if(niv[fiu]==0)
        {
            dfsst(fiu);
            low[nod]=min(low[nod], low[fiu]);
        }else
        {
            if(is[fiu])
                low[nod]=min(low[nod], low[fiu]);
        }
    }
    if(niv[nod]==low[nod])
        scc(nod);
}
ifstream in("ctc.in");
ofstream out("ctc.out");
int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y;
        L[x].push_back(y);
    }
    for(i=1; i<=n; i++)
    {
        if(niv[i]==0)
        {
            dfsst(i);
        }
    }
    out<<nrst<<"\n";
    for(i=1; i<=nrst; i++)
    {
        for(j=0; j<st[i].size(); j++)
            out<<st[i][j]<<" ";
        out<<"\n";
    }
    return 0;
}