Cod sursa(job #1639961)

Utilizator clopotelNeamtu Sergiu clopotel Data 8 martie 2016 14:58:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
FILE* f=fopen("ctc.in","r");
FILE* g=fopen("ctc.out","w");
int n,m,qq,qqq,t;
bool viz[100001];
stack <int> st;
vector <int> v[100001];
vector <int> v2[100001];
vector <int> ght[100001];
void dfs1(int x)
{
    viz[x]=true;
    for(int i=0; i<v[x].size(); i++)
        if(!viz[v[x][i]])
            dfs1(v[x][i]);
    st.push(x);
}
void dfs2(int x)
{
    viz[x]=false;
    ght[t].push_back(x);
        for(int i=0; i<v2[x].size(); i++)
        if(viz[v2[x][i]])
            dfs2(v2[x][i]);

}
void inv()
{
    for(int i=1; i<=n; i++)
        for(int j=0; j<v[i].size(); j++)
            if(v[v[i][j]].size())
                v2[v[i][j]].push_back(i);
}
int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        fscanf(f,"%d%d",&qq,&qqq);
        v[qq].push_back(qqq);
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
        {
            dfs1(i);
        }
    inv();
    while(!st.empty())
    {

        if(viz[st.top()])
            dfs2(st.top()),t++;
        st.pop();
    }
    fprintf(g,"%d\n",t);
    for(int i=0;i<t;i++)
    {
        for(int j=ght[i].size()-1;j>=0;j--)
        {
            fprintf(g,"%d ",ght[i][j]);
        }
        fprintf(g,"\n");
    }

    return 0;
}