Cod sursa(job #2668100)

Utilizator anacomoAna-Maria Comorasu anacomo Data 4 noiembrie 2020 14:49:53
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;

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

stack<int> stiva;
vector<int> result[10000000];
int culoare;

void DFS(int node, vector<int> &visited, vector<int> fii[])
{
    visited[node] = true;
    for (int i = 0; i < fii[node].size(); ++i)
        if (visited[fii[node][i]] == 0)
            DFS(fii[node][i], visited, fii);
    stiva.push(node);
}

void DFS2(int node, vector<int> &visited, vector<int> parinti[])
{
    visited[node] = true;
    result[culoare].push_back(node);
    for (int i = 0; i < parinti[node].size(); ++i)
        if (visited[parinti[node][i]] == false)
            DFS2(parinti[node][i], visited, parinti);
}

int main()
{
    int n, m;
    fin >> n >> m;

    vector<int> fii[n + 1];
    vector<int> parinti[n + 1];
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        fin >> x >> y;
        fii[x].push_back(y);
        parinti[y].push_back(x);
    }

    vector<int> visited(n + 1);
    for (int i = 1; i <= n; ++i)
        if (visited[i] == 0)
            DFS(i, visited, fii);

    for (int i = 1; i <= n; ++i)
        visited[i] = 0;

    while (!stiva.empty())
    {
        int node = stiva.top();
        if (visited[node] == false)
        {
            culoare++;
            DFS2(node, visited, parinti);
        }
        stiva.pop();
    }

    fout << culoare << '\n';
    for (int i = 1; i <= culoare; ++i)
    {
        for (int j = 0; j < result[i].size(); j++)
            fout << result[i][j] << " ";
        fout << endl;
    }

    fin.close();
    fout.close();
    return 0;
}