Cod sursa(job #950931)

Utilizator cdascaluDascalu Cristian cdascalu Data 18 mai 2013 18:59:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define Nmax 100001
using namespace std;

vector<int> G[Nmax],GT[Nmax];
int viz[Nmax],N,M;
stack<int> st;
vector<int> comp;
vector< vector<int> > sol;
void read_data()
{
    FILE*f = fopen("ctc.in","r");
    fscanf(f,"%d%d",&N,&M);
    int x,y;
    while(M--)
    {
        fscanf(f,"%d%d",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    fclose(f);
}
void dfs_one(int node)
{
    viz[node] = 1;
    for(vector<int>::iterator it = G[node].begin();it!=G[node].end();++it)
        if(viz[*it] == 0)
            dfs_one(*it);

    st.push(node);
}
void dfs_two(int node)
{
    viz[node] = -1;
    for(vector<int>::iterator it = GT[node].begin();it!=GT[node].end();++it)
        if(viz[*it] != -1)
            dfs_two(*it);
    comp.push_back(node);
}
void solve()
{
    for(int i=1;i<=N;++i)
        if(!viz[i])
            dfs_one(i);
    int elem;
    while(!st.empty())
    {
        elem = st.top();st.pop();
        if(viz[elem] != -1)
        {
            dfs_two(elem);
            sol.push_back(comp);
            comp.clear();
        }
    }
}
void write_data()
{
    FILE*g = fopen("ctc.out","w");
    fprintf(g,"%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(g,"%d ", *it);
        fprintf(g,"\n");
    }
    fclose(g);
}
int main()
{
    read_data();
    solve();
    write_data();
    return 0;
}