Cod sursa(job #2324689)

Utilizator OveehMariciuc Ovidiu Oveeh Data 21 ianuarie 2019 12:40:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <stack>
#include <vector>
#define nmax 100001

using namespace std;

FILE *f,*g;

int n,m;
bool viz1[nmax],viz2[nmax];
stack <int> S;
vector <int> V[nmax];
vector <int> Vt[nmax];
vector <int> V2[nmax];

void Citire()
{
    int i,x,y;
    fscanf(f,"%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        fscanf(f,"%d%d",&x,&y);
        V[x].push_back(y);
        Vt[y].push_back(x);
    }
}

void DFS1(int x)
{
    int i;
    vector <int>::iterator it;
    viz1[x]=1;
    for(it=V[x].begin(); it!=V[x].end(); it++)
        if(!viz1[*it]) DFS1(*it);
    S.push(x);
}

void DFS2(int x, int k)
{
    int i;
    vector <int>::iterator it;
    viz2[x]=1;
    for(it=Vt[x].begin(); it!=Vt[x].end(); it++)
        if(!viz2[*it]) DFS2(*it,k);
    V2[k].push_back(x);
}


int main()
{
    int c,k=0,i;
    vector <int>::iterator it;
    f=fopen("ctc.in","r");
    g=fopen("ctc.out","w");
    Citire();
    fclose(f);
    for(i=1; i<=n; i++)
        if(viz1[i]==0) DFS1(i);
    while(!S.empty())
    {
        c=S.top();
        S.pop();
        if(viz2[c]==0)
        {
            k++;
            DFS2(c,k);
        }
    }
    fprintf(g,"%d",k);
    fprintf(g,"\n");
    for(i=1; i<=n; i++)
    {
        for(it=V2[i].begin(); it!=V2[i].end(); ++it)
            fprintf(g,"%d ",*it);
        fprintf(g,"\n");
    }
    return 0;
}