Cod sursa(job #874336)

Utilizator TeOOOVoina Teodora TeOOO Data 8 februarie 2013 10:41:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;

//Constante
const int sz = (int)1e5+1;

//Functii
void dfs(int node);
void printDFS(int node);

FILE *in,*out;

int nodes, edges;
bool visited[sz];
bool inStack[sz];

vector <int> graph[sz], reversedGraph[sz];
stack <int> st;

vector< vector<int> > answer;
vector<int> answerTemp;

int main()
{
    in=fopen("ctc.in","rt");
    out=fopen("ctc.out","wt");
    fscanf(in,"%d%d",&nodes,&edges);
    for(int i=1; i<=edges; ++i)
    {
        int rFrom, rTo;
        fscanf(in,"%d%d",&rFrom,&rTo);
        graph[rFrom].push_back(rTo);
        reversedGraph[rTo].push_back(rFrom);
    }

    for(int i=1; i<=nodes; ++i)
        if(!inStack[i])
            dfs(i);

    while(!st.empty())
    {
        int current = st.top();
        st.pop();

        if(inStack[current])
        {
            printDFS(current);
            answer.push_back(answerTemp);
            answerTemp.clear();
        }
    }
    fprintf(out,"%d\n",answer.size());

    vector< vector<int> >::iterator vit, vend = answer.end();
    for(vit=answer.begin(); vit!=vend; ++vit)
    {
        vector<int>::iterator it, end = vit->end();
        for(it=vit->begin(); it!=end; ++it)
            fprintf(out,"%d ",*it);
        fprintf(out,"\n");
    }

    fclose(in);
    fclose(out);
    return 0;
}

void dfs(int node)
{
    visited[node] = true;

    vector<int>::iterator it, end = graph[node].end();

    for(it=graph[node].begin(); it!=end; ++it)
        if(!visited[*it])
            dfs(*it);

    st.push(node);
    inStack[node] = true;
}
void printDFS(int node)
{
    inStack[node] = false;
    answerTemp.push_back(node);

    vector<int>::iterator it, end = reversedGraph[node].end();
    for(it=reversedGraph[node].begin(); it!=end; ++it)
        if(inStack[*it])
            printDFS(*it);
}