Cod sursa(job #595813)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 14 iunie 2011 14:06:32
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

vector <int> g[100005],con;
vector < vector <int> > c;
stack <int> s;
int index,in_stack[100005],idx[100005],lowlink[100005];

void tarjan(int x)
{
    unsigned int i;
    lowlink[x]=index;
    idx[x]=lowlink[x];
    ++index;
    s.push(x),in_stack[x]=1;
    for (i=0;i<g[x].size();++i)
        if (idx[g[x][i]]==-1)
        {
            tarjan(g[x][i]);
            lowlink[x]=min(lowlink[x],lowlink[g[x][i]]);
        }
        else if (in_stack[g[x][i]])
            lowlink[x]=min(lowlink[x],lowlink[g[x][i]]);
    if (idx[x]==lowlink[x])
    {
        con.clear();
        int node;
        do
        {
            con.push_back(node=s.top());
            s.pop(),in_stack[node]=0;
        }
        while (node!=x);
        c.push_back(con);
    }
}

int main(void)
{
    int n,cnt_edges,x,y;
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    in>>n;
    for (in>>cnt_edges;cnt_edges>0;--cnt_edges)
    {
        in>>x>>y;
        g[x-1].push_back(y-1);
    }
    idx.assign(n,-1),in_stack.assign(n,0);
    for (int i=0;i<n;++i)
        if (idx[i]==-1)
            tarjan(i);
    out<<c.size()<<"\n";
    for (size_t i=0;i<c.size();++i)
    {
        for (size_t j=0;j<c[i].size();++j)
            out<<c[i][j]+1<<" ";
        out<<"\n";
    }
    return 0;
}