Cod sursa(job #1283249)

Utilizator blue_skyPetrica Stefan Cosmin blue_sky Data 5 decembrie 2014 14:07:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <list>
#include <stack>
#define DIM 100001

using namespace std;

list <int> nod[DIM],inv[DIM],sol[DIM];
stack <int> st;
bool v[DIM],w[DIM];
int n,m,x,y,cr;

void DFS(int k)
{
    v[k]=1;
    for(list<int>::iterator i=nod[k].begin();i!=nod[k].end();++i)
    {
        if(!v[*i])
            DFS(*i);
    }
    st.push(k);
}
void DFST(int k)
{
    w[k]=1;
    sol[cr].push_back(k);
    for(list<int>::iterator i=inv[k].begin();i!=inv[k].end();++i)
    {
        if(!w[*i])
            DFST(*i);
    }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        nod[x].push_back(y);
        inv[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!v[i]) DFS(i);

    while(!st.empty())
    {
        int vf=st.top();
        if(!w[vf])
        {
            ++cr;
            DFST(vf);
        }
        st.pop();
    }
    g<<cr<<'\n';
    for(int i=1;i<=cr;++i)
    {
        for(list<int>::iterator j=sol[i].begin();j!=sol[i].end();++j)
            g<<*j<<" ";
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}