Cod sursa(job #735836)

Utilizator visanrVisan Radu visanr Data 17 aprilie 2012 13:07:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;


#define nmax 100010

int index[nmax],lowLink[nmax];
stack<int> s;
vector<int> graph[nmax];
vector< vector<int> > components;
int nodes,edges,to,from,NumberOfNodes=1;
vector<bool> InStack(nmax);

void Tarjan(int StartNode);


int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%i %i", &nodes,&edges);
    for(int i=0;i<edges;i++)
    {
            scanf("%i %i", &to,&from);
            graph[from].push_back(to);
    }
    for(int i=1;i<=nodes;i++)
    {
            if(index[i]==0)
            {
                               Tarjan(i);
            }
    }
    printf("%i\n", components.size());
    for(int i=0;i<components.size();i++)
    {
            for(int j=components[i].size()-1;j>=0;j--)
            {
                    printf("%i ", components[i][j]);
            }
            printf("\n");
    }
    int i;
    //scanf("%i", &i);
    return 0;
}

void Tarjan(int StartNode)
{
     index[StartNode]=lowLink[StartNode]=NumberOfNodes++;
     s.push(StartNode);
     InStack[StartNode]=true;
     vector<int> :: iterator it;
     for(it=graph[StartNode].begin();it!=graph[StartNode].end();++it)
     {
               if(index[*it]==0)
               {
                                Tarjan(*it);
                                lowLink[StartNode]=min(lowLink[StartNode],lowLink[*it]);
               }else
               {
                    if(InStack[*it]==true)
                    {
                                           lowLink[StartNode]=min(lowLink[StartNode],index[*it]);
                    }
               }
     }
     if(index[StartNode]==lowLink[StartNode])
     {
                    vector<int> NewComponent;
                    int node=0;
                    while(node!=StartNode)
                    {
                                          node=s.top();
                                          s.pop();
                                          InStack[node]=false;
                                          NewComponent.push_back(node);
                    }
                    components.push_back(NewComponent);
     }
}