Cod sursa(job #1456722)

Utilizator Liviu98Dinca Liviu Liviu98 Data 1 iulie 2015 19:14:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <stack>
#define NMax 100010
using namespace std;
int nodes,edges,prenum[NMax],low[NMax],inc,k;
bool mark[NMax],inStack[NMax];
vector<int> Graf[NMax],Sol[NMax];
stack<int> S;

int Min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

void Tarjan(int node)
{
    mark[node]=true;

    S.push(node);
    inStack[node]=true;

    prenum[node]=++inc;
    low[node]=prenum[node];

    for(vector<int>::iterator it=Graf[node].begin();it!=Graf[node].end();it++)
    {
        if(mark[*it]==false)
        {
            Tarjan(*it);
            low[node]=Min(low[node],low[*it]);
        }
        else
            if(inStack[*it])
            {
                low[node]=Min(low[node],prenum[*it]);
            }
    }

    if(low[node]==prenum[node])
    {
        int u;
        k++;
        do
        {
            u=S.top();
            Sol[k].push_back(u);
            inStack[u]=false;
            S.pop();
        }
        while(u!=node);
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&nodes,&edges);
    int x,y;
    for(int i=1;i<=edges;i++)
    {
        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
    }

    for(int i=1;i<=nodes;i++)
        if(mark[i]==false)
        Tarjan(i);


    printf("%d\n",k);
    for(int i=1;i<=k;i++)
    {
        for(vector<int>::iterator it=Sol[i].begin();it!=Sol[i].end();it++)
            printf("%d ",*it);
        printf("\n");
    }
}