Cod sursa(job #1930216)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 18 martie 2017 16:52:17
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define z(x) (x & (-x))

typedef long long ll;

using namespace std;

int n, m, x, y, v;

vector < int > V[100100], I[100100], T[100100];
bool taken[100100];
char a[100100], b[100100];

void dfs(int x)
{
    a[x] = '+';
    for (auto it : V[x])
        if (a[it] != '+') dfs(it);
}

void dfs2(int x)
{
    b[x] = '-';
    for (auto it : I[x])
        if (b[it] != '-') dfs2(it);
}

void dfs12(int x)
{
    dfs(x);
    dfs2(x);
    ++v;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '+' && b[i] == '-') T[v].push_back(i), taken[i] = 1;
        a[i] = b[i] = 0; 
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> x >> y, V[x].push_back(y), I[y].push_back(x);
    for (int i = 1; i <= n; i++)
        if (!taken[i]) dfs12(i);
    cout << v;
    for (auto it : T)
    {
        for (auto it2 : it)
            cout << it2 << " ";
        cout << "\n";
    }
    return 0;
}