Cod sursa(job #1597607)

Utilizator SmitOanea Smit Andrei Smit Data 12 februarie 2016 10:09:16
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

int n,m,ind,t[5003],t2[5003],ind2,sol;
bool viz[5003];
vector<int>L[5003],L2[5003],a[5003];

inline void Citire()
{
    int i,x,y;
    ifstream fin("ctc.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y;
        L[x].push_back(y);
        L2[y].push_back(x);
    }
    fin.close();
}

inline void DFS(int x)
{
    int y;
    unsigned int k;
    viz[x]=true;
    for(k=0;k<L[x].size();++k)
    {
        y=L[x][k];
        if(!viz[y]) DFS(y);
    }
    t[++ind]=x;
}

inline void DFS2(int x)
{
    int y;
    unsigned int k;
    viz[x]=true;
    for(k=0;k<L2[x].size();++k)
    {
        y=L2[x][k];
        if(!viz[y]) DFS2(y);
    }
    a[sol].push_back(x);
}

inline void Sortare()
{
    int i;
    for(i=1;i<=n;++i)
        if(!viz[i])
            DFS(i);
}

inline void Reinit()
{
    int i;
    for(i=1;i<=n;++i)   viz[i]=false;
}

int main()
{
    int i,x;
    unsigned int j;
    Citire();
    Sortare();
    Reinit();
    for(i=n;i>=1;--i)
    {
        x=t[i];
        if(!viz[x])
        {
            sol++;
            DFS2(x);
        }
    }
    ///////////////////////////
    ofstream fout("ctc.out");
    fout<<sol<<"\n";
    for(i=1;i<=sol;++i)
    {
        for(j=0;j<a[i].size();++j)
            fout<<a[i][j]<<" ";
        fout<<"\n";
    }
    fout.close();
    return 0;
}