Cod sursa(job #1412900)

Utilizator Vladut-Vlad Panait Vladut- Data 1 aprilie 2015 17:15:35
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <stack>
#define maxn 100005

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector <int> v[maxn];
vector <int> g[maxn];
stack <int> st;

int n, m, x, y, depth[maxn], lowlink[maxn], nrctc=0;
bool viz[maxn], in_stack[maxn];

void dfs(int x, int lvl)
{
    viz[x]=1;
    st.push(x);
    in_stack[x]=1;
    depth[x]=lvl;
    lowlink[x]=lvl;

    for(int i=0; i<g[x].size(); i++)
    {
        int y=g[x][i];
        if(!viz[y])
        {
            dfs(y, lvl+1);
            lowlink[x]=min(lowlink[x], lowlink[y]);
        }
        else if(in_stack[y])
            lowlink[x]=min(lowlink[x], lowlink[y]);
    }
int k=0;
    if(depth[x]==lowlink[x])
    {
        nrctc++;
        while(st.top()!=x)
        {
            v[nrctc].push_back(st.top());
            in_stack[st.top()]=0;
            st.pop();
        }
        v[nrctc].push_back(x);
        st.pop();
        in_stack[x]=0;
    }
}



int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
    }

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

    fout << nrctc << '\n';

    for(int i=1; i<=nrctc; i++)
    {
        for(int j=0; j<v[i].size(); j++)
            fout << v[i][j] << ' ';
        fout << '\n';
    }

    return 0;
}