Cod sursa(job #2354514)

Utilizator RadulescuRichardAndreiRadulescu Richard- Andrei RadulescuRichardAndrei Data 25 februarie 2019 12:46:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NRMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,nr,nrc;

vector <int> L[NRMAX];
vector <int> T[NRMAX];
vector <int> CTC[NRMAX];
bool uz[NRMAX];
int post[NRMAX];


void citire();
void dfs(int x);
void dfst(int x);
void afisare();
int main()
{
    int i;

    citire();
    for(i=1;i<=n;i++)
        if(uz[i]==0)
           dfs(i);

    for(i=n;i>=0;i--)
        if(uz[post[i]]==1)
            {nrc++;
             dfst(post[i]);

            }
afisare();
    return 0;
}

void citire()
{
int i,v1,v2;

    fin>>n>>m;

    for(i=0;i<m;i++)
        {
            fin>>v1>>v2;
            L[v1].push_back(v2);
            T[v2].push_back(v1);


        }

}

void dfs(int x)
{
    int i;

    uz[x]=1;

    for(i=0;i<L[x].size();i++)
        if(uz[L[x][i]]==0)
            dfs(L[x][i]);

    nr++;
    post[nr]=x;
}

void dfst(int x)
{

    int i;

    uz[x]=0;
    CTC[nrc].push_back(x);

    for(i=0;i<T[x].size();i++)
        if(uz[T[x][i]]==1)
            dfst(T[x][i]);

}

void afisare()
{
    int i,j;

    fout<<nrc<<'\n';

    for(i=1;i<=nrc;i++)
        {
            for(j=0;j<CTC[i].size();j++)
                fout<<CTC[i][j]<<' ';
        fout<<'\n';
        }
}