Cod sursa(job #912441)

Utilizator AndreiTeodorAndrei R AndreiTeodor Data 12 martie 2013 13:50:01
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

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

const int maxn = 200001;
int num_vertices,num_edges,index,num_ctc;
int ind[maxn],in_stack[maxn],low[maxn];
vector<int> graph[maxn],con[maxn];
stack<int> s;

int Minim(int a,int b)
{
    if(a>b) return b;
    return a;
}

void StrongConnect(int v)
{
    ind[v] = index;
    low[v] = index;
    index++;
    s.push(v);
    in_stack[v]=1;

    vector<int>::iterator it;
    for(it=graph[v].begin(); it!=graph[v].end(); it++)
        if(!ind[*it])
        {
            StrongConnect(*it);
            low[v] = Minim(low[v],low[*it]);
        }
        else
            if(in_stack[*it])
                low[v] = Minim(low[v],ind[*it]);

    if(ind[v]==low[v])
    {
        num_ctc++;
        int node;
        do{
            node = s.top();
            s.pop();
            in_stack[node]=0;
            con[num_ctc].push_back(node);
        }while(node!=v);
    }
}

int main()
{
    int i,aux1,aux2;
    vector<int>::iterator it;

    f>>num_vertices>>num_edges;

    for(i=1;i<=num_edges;i++)
    {
        f>>aux1>>aux2;
        graph[aux1].push_back(aux2);
    }

    for(i=1;i<=num_vertices;i++)
        if(!ind[i])
            StrongConnect(i);

    g<<num_ctc<<'\n';
    for(i=1;i<=num_ctc;i++)
    {
        for(it=con[i].begin();it!=con[i].end();it++)
            g<<*it<<' ';
        g<<'\n';
    }

/*
    for(i=1;i<=num_vertices;i++)
        g<<ind[i]<<' ';
    g<<'\n';
    for(i=1;i<=num_vertices;i++)
        g<<low[i]<<' ';
    g<<'\n';*/

    return 0;
}