Cod sursa(job #3254269)

Utilizator M132M132 M132 M132 Data 6 noiembrie 2024 20:33:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("ctc.in");
ofstream g ("ctc.out");

const int nmax = 100000;
vector <int> vecini[nmax+5], veciniGT[nmax+5], sortare, componente[nmax + 5];
int vizitat[nmax + 5];

void dfs(int node, vector <int> muchii[nmax+5], vector <int> &Sortare)
{
    ///sortare o sa fie la final vectoul cu ordinea varfurilor (prima data)
    ///a doua data o sa fie componenta tare conexa in care pun varfurile
    vizitat[node] = 1;
    int i;
    for(i = 0; i < muchii[node].size(); ++i)
    {
        int nodnou = muchii[node][i];
        if(!vizitat[nodnou])
        {
            dfs(nodnou, muchii, Sortare);
        }
    }
    Sortare.push_back(node);
}

int main()
{
    int n, m, i, x, y, conexe = 0;
    f >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        f >> x >> y;
        vecini[x].push_back(y);
        veciniGT[y].push_back(x);
    }
    ///dfs 1
    ///fac vizitat pe 0
    ///dfs 2
    for(i = 1; i <= n; ++i)
    {
        if(!vizitat[i])
        {
            dfs(i, vecini, sortare);
        }
    }
    for(i = 1; i <= n; ++i)
    {
        vizitat[i] = 0;
    }
    for(i = n - 1; i >= 0; --i)
    {
        if(!vizitat[sortare[i]])
        {
            ++conexe;
            dfs(sortare[i], veciniGT, componente[conexe]);
        }
    }
    g << conexe << "\n";
    for(i = 1; i <= conexe; ++i)
    {
        int j;
        for(j = 0; j < componente[i].size(); ++j)
        {
            g << componente[i][j] << " ";
        }
        g << "\n";
    }
    return 0;
}