Cod sursa(job #2298408)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 8 decembrie 2018 09:48:05
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
//
//  main.cpp
//  Ctc
//
//  Created by Darius Buhai on 08/12/2018.
//  Copyright © 2018 Darius Buhai. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

vector<int> a[100001], sol[100001],orig[100001];
int n, m, ctc, counter, k;
int temp[100001],viz[100001];

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

void read()
{
    fin>>n>>m;
    for(int i=0;i<m;i++){
        int x, y;
        fin>>x>>y;
        orig[x].push_back(y);
        a[y].push_back(x);
    }
}

void dfp(int x)
{
    viz[x]=1;
    for(auto i:orig[x])
        if(!viz[i])
            dfp(i);
    temp[k++] = x;
}

void dfm(int x)
{
    viz[x]=0;
    sol[counter].push_back(x);
    for(auto i:a[x])
        if(viz[i])
            dfm(i);
}

void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(viz[i] == 0)
            dfp(i);
    
    for(int i=k; i>=1; i--)
        if(viz[temp[i]]==1){
            counter++;
            dfm(temp[i]);
        }
    
    fout<<counter<<"\n";
    for(int i = 1; i <= counter; i++)
    {
        for(int j = 0; j < sol[i].size(); j++)
            fout<<sol[i][j]<< " ";
        fout<<"\n";
    }
}

int main() {
    read();
    kosaraju();
    return 0;
}