Cod sursa(job #936164)

Utilizator vladm97Matei Vlad vladm97 Data 5 aprilie 2013 20:12:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<vector>
#include<stack>
#define lmax 110000
using namespace std;

vector<int>v1[lmax];
vector<int>v2[lmax];
vector<int>v[lmax];
int k;
int parcurs1[lmax];
int parcurs2[lmax];
stack<int>s;
ofstream g("ctc.out");
void df1(int a)
{
    int i;
    parcurs1[a]=1;
    for(i=0;i<v1[a].size();i++)
    {
        if(parcurs1[v1[a][i]]==0)df1(v1[a][i]);
    }
    s.push(a);
}
void df2(int a)
{   v[k].push_back(a);
    parcurs2[a]=1;
    int i;
    for(i=0;i<v2[a].size();i++)
    {
        if(parcurs2[v2[a][i]]==0)
            df2(v2[a][i]);
    }
}
main()
{
    int n,m,a,b,i,j;
    ifstream f("ctc.in");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v1[a].push_back(b);
        v2[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        if(parcurs1[i]==0)df1(i);
    while(!s.empty())
    {
        if(parcurs2[s.top()]==0)
            {
                k++;
                df2(s.top());
            }
       s.pop();
    }
    g<<k<<"\n";
    for(i=1;i<=k;i++)
    {
        for(j=0;j<v[i].size();j++)
            g<<v[i][j]<<" ";
            g<<"\n";
    }
}