Cod sursa(job #1397533)

Utilizator misinozzz zzz misino Data 23 martie 2015 16:31:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<fstream>
#include<stack>
#include<vector>

#define N 100100

using namespace std;

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

int x,n,y,nrctc,m,i,viz[N];

vector<int>v[N],vt[N],sol[N];
stack<int>st;

inline void dfs(int x){
    viz[x] = 1;

    for(vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
        if(!viz[*it])
            dfs(*it);

    st.push(x);
}

inline void dfst(int x){
    viz[x] = 0;
    sol[nrctc].push_back(x);

    for(vector<int>::iterator it = vt[x].begin(); it != vt[x].end(); ++it)
        if(viz[*it])
            dfst(*it);
}

int main()
{
    f >> n >> m;

    for(i = 1; i <= m; ++i)
    {
        f >> x >> y;

        v[x].push_back(y);
        vt[y].push_back(x);
    }

    for(i = 1; i <= n; ++i)
        if(!viz[i])
            dfs(i);

    while(!st.empty())
    {
        while(!st.empty() && !viz[st.top()])
            st.pop();

        if(st.empty())
            break;

        ++nrctc;
        dfst(st.top());
        st.pop();
    }

    g << nrctc << '\n';

    for(i = 1; i <= nrctc; ++i, g << '\n')
        for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
            g << *it << ' ';

    return 0;
}