Cod sursa(job #2540998)

Utilizator razvan123vRazvan Vranceanu razvan123v Data 7 februarie 2020 22:05:26
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
//
//  main.cpp
//  kosaraju
//
//  Created by Razvan Vranceanu on 07/02/2020.
//  Copyright © 2020 Razvan Vranceanu. All rights reserved.
//

#include <fstream>
#define N 100002
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, q[N], poz, nr;
bool vizG[N];
int vizGT[N];
struct nod{
    int x;
    nod *leg;
} *L[N], *LGT[N];

void adauga(nod *&pp, int val)
{
    nod *p = new nod;
    p -> x = val;
    p -> leg =pp;
    pp=p;
}

void citire()
{
    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        adauga(L[x], y);
    }
    
}

void GfTr()
{
    nod *p;
    for(int i=1;i<=n;i++)
        for(p=L[i]; p; p=p->leg)
            adauga(LGT[p->x], i);
}
void DF(int i)
{
    vizG[i]=1;
    for(nod *p=L[i]; p; p=p->leg)
        if(!vizG[p->x])
            DF(p->x);
    q[++poz]=i;
}
void DFGT(int i, int nr)
{
    vizGT[i]=nr;
    nod *p;
    for(p=LGT[i];p;p=p->leg)
        if(vizGT[p->x] == 0)
            DFGT(p->x, nr);
}
int main()
{
    citire();
    GfTr();
    for(int i=1;i<=n;i++)
        if(!vizG[i])
            DF(i);
    int contor=0;
    for(int i=poz; i>=1; i--)
        if(!vizGT[q[i]])
        {
            contor++;
            DFGT(q[i], contor);
        }
    
    g<<contor;
    int k=0;
    while(k<=contor)
    {
        for(int i=1;i<=n;i++)
            if(vizGT[i] == k)
                g<<i<<" ";
        g<<'\n';
        k++;
    }
   
    return 0;
}