Cod sursa(job #1179528)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 28 aprilie 2014 20:06:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include<fstream>
#include<vector>
#include<bitset>
#include<stack>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,pos,str;
vector<int>vin[100005];
vector<int>pleaca[100005];
vector<int>componente[100005];
stack<int>S;
bitset<100005>viz;

inline void Citire()
{
    int i,x,y;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            pleaca[x].push_back(y);
            vin[y].push_back(x);
        }
}

inline void DFS(int x)
{
    int i,len;
    viz[x]=1;
    len=pleaca[x].size();
    for (i=0;i<len;i++)
        if (!viz[pleaca[x][i]])
            DFS(pleaca[x][i]);
    S.push(x);
}

inline void DFS_t(int x)
{
    int i,len;
    viz[x]=1;
    len=vin[x].size();
    componente[str].push_back(x);
    for (i=0;i<len;i++)
        if (!viz[vin[x][i]])
            DFS_t(vin[x][i]);
}

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

inline void Parcurgere_t()
{
    int i;
    for (i=1;i<=n;i++) viz[i]=0;
    while (!S.empty())
        {
            if (viz[S.top()]==0)
                {
                    str++;
                    DFS_t(S.top());
                }
            S.pop();
        }
}

inline void Afisare()
{
    int i,j,len;
    fout<<str<<"\n";
    for (i=1;i<=str;i++)
        {
            len=componente[i].size();
            for (j=0;j<len;j++)
                fout<<componente[i][j]<<" ";
            fout<<"\n";
        }
}

int main()
{
    Citire();
    Parcurgere();
    Parcurgere_t();
    Afisare();
    return 0;
}