Cod sursa(job #2354690)

Utilizator petrea1551Petrea Calin petrea1551 Data 25 februarie 2019 15:05:32
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

char viz[100001];
int k, n, m;
vector <int> v1[100001], v2[100001];

void dfs1(int nod)
{
    viz[nod]++;
    for (int i = 0; i < v1[nod].size(); i++)
        if (viz[v1[nod][i]] == 0)
            dfs1(v1[nod][i]);
}

void dfs2(int nod)
{
    viz[nod]++;
    for (int i = 0; i < v2[nod].size(); i++)
        if (viz[v2[nod][i]] == 1)
            dfs2(v2[nod][i]);
}

int main()
{
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    cin >> n >> m;
    stack <int> q[n];
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
        {
            k++;
            dfs1(i);
            dfs2(i);
            for (int j = 1; j <= n; j++)
            {
                if (viz[j] == 2)
                {
                    q[k].push(j);
                    viz[j] = -1;
                }
                if (viz[j] != -1)
                    viz[j] = 0;
            }
        }
    cout << k << '\n';
    for (int i = 1; i <= k; i++)
    {
        while (!q[i].empty())
            cout << q[i].top() << ' ', q[i].pop();
        cout << '\n';
    }
    return 0;
}