Cod sursa(job #952476)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 15:52:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <stack>
#include <vector>
using namespace std;
  
vector<int> graf[100001],graft[100001];
int viz[100001],N,M;
stack<int> stiva;
vector<int> componenta;
vector< vector<int> > sol;
 
void citire()
{
    FILE*f = fopen("ctc.in","r");
    fscanf(f,"%d%d",&N,&M);
    int x,y;
    while(M != 0)
    {
        M--;
        fscanf(f,"%d%d",&x,&y);
        graf[x].push_back(y);
        graft[y].push_back(x);
    }
    fclose(f);
}
 
void df1(int node)
{
    viz[node] = 1;
    for(vector<int>::iterator it = graf[node].begin(); it != graf[node].end(); it++)
        if(viz[*it] == 0)
            df1(*it);
  
    stiva.push(node);
}
 
void df2(int node)
{
    viz[node] = -1;
    for(vector<int>::iterator it = graft[node].begin(); it != graft[node].end(); it++)
        if(viz[*it] != -1)
            df2(*it);
    componenta.push_back(node);
}
 
void algraf()
{
    for(int i = 1; i <= N; ++i)
        if(!viz[i])
            df1(i);
    int elem;
    while(!stiva.empty())
    {
        elem = stiva.top();
        stiva.pop();
        if(viz[elem] != -1)
        {
            df2(elem);
            sol.push_back(componenta);
            componenta.clear();
        }
    }
}
 
void afisare()
{
    FILE*graf = fopen("ctc.out","w");
    fprintf(graf,"%d\n", sol.size());
    for(int i = 0, size = sol.size() ; i < size ; ++i)
    {
        for(vector< int >::iterator it = sol[i].begin(); it != sol[i].end(); it++)
            fprintf(graf,"%d ", *it);
        fprintf(graf,"\n");
    }
    fclose(graf);
}
 
int main()
{
    citire();
    algraf();
    afisare();
    return 0;
}