Cod sursa(job #1068991)

Utilizator dumytruKana Banana dumytru Data 29 decembrie 2013 09:54:49
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <fstream>

#include <algorithm>
#include <vector>
#include <stack>

#define Nmax 100000
#define Mmax 200000

using namespace std;

unsigned n,m,current_time;
vector<vector<unsigned> > graf, graf_rev,solutie;
vector<unsigned> time,is_visited,time_rev;
stack<unsigned> coada;

void DFS_Rev(unsigned start_node)
{
    unsigned len,i;

    is_visited[start_node]=1;
    len = graf_rev[start_node].size();
    for(i=0; i<len;i++)
        if(!is_visited[graf_rev[start_node][i]])
            DFS_Rev(graf_rev[start_node][i]);
    time[start_node] = ++current_time;
}


void time_table()
{
    int i;
    current_time=0;
    for(i=n;i>0;i--)
    {
        if(is_visited[i]==0){
            DFS_Rev(i);
        }
    }
}

void DFS(unsigned start_node)
{
    unsigned len,i;

    is_visited[start_node]=1;
    len = graf[start_node].size();
    for(i=0; i<len;i++)
        if(!is_visited[graf[start_node][i]])
            DFS(graf[start_node][i]);
    time.push_back(start_node);
}

void find_dag()
{
    int i;
    for(i=n;i>0;i--)
    {
        if(is_visited[time_rev[i]]==0){
            time.clear();
            DFS(time_rev[i]);
            solutie.push_back(time);
        }
    }
}

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

    unsigned i,j,u,v,len;

    //citire
    f>>n>>m;

    graf.resize(n+1);graf_rev.resize(n+1);time.resize(n+1);is_visited.resize(n+1);
    for(i=1;i<=m;i++)
    {
        f>>u>>v;
        graf[u].push_back(v);
        graf_rev[v].push_back(u);
    }

    time_table();
    time_rev.resize(n+1);
    for(i=1;i<=n;i++)
    {
        time_rev[time[i]] = i;

    }
    is_visited.clear();is_visited.resize(n+1);
    find_dag();
    unsigned solutie_size = solutie.size();
    g<<solutie_size<<'\n';
    for(i=0;i<solutie_size;i++)
    {
        len = solutie[i].size();
        sort(solutie[i].begin(), solutie[i].end());
        for(j=0;j<len;j++)
            g<<solutie[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}