Cod sursa(job #1288743)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 9 decembrie 2014 00:57:36
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdio>
#define N 100005
#define M 200005
bool stack[N];
int index[N];
int min[N];
int contor = 1;
std::stack<int> s;
std::vector<std::vector<int> > v;
std::vector<std::vector<int> >components;

void dfs(int k)
{
    s.push(k);
    index[k] = min[k] = contor++; 
    for(auto& e: v[k]) 
    {
        if(not index[e])
        {
            dfs(e);
        }
        min[k] = std::min(min[k], min[e]);
    }

    if(min[k] == index[k])
    {
        std::vector<int> component;
        while(s.top()!=k)
        {
            component.push_back(s.top());
            s.pop();
        }
        component.push_back(k);
        s.pop();
        components.push_back(component);
    }
}

int main ()
{
    FILE *fin=fopen("ctc.in","r");
    FILE *fout=fopen("ctc.out","w");

    int n,m,a,b;

    fscanf(fin, "%d%d", &n, &m);

    v.resize(n+1);
    for(int i=0;i<m;i++)
    {
       fscanf(fin, "%d%d", &a, &b); 
       v[a].push_back(b);
    }

    for(int i=1;i<=n;i++)
    {
        if(not index[i])
        {
           dfs(i); 
        }
    }
    std::cout<<components.size()<<std::endl;
    for(auto& component: components)
    {
        for(auto& e: component)
        {
            std::cout<<e<<" ";
        }
        std::cout<<std::endl;
    }
    return 0;
}