Cod sursa(job #2784603)

Utilizator realmeabefirhuja petru realmeabefir Data 16 octombrie 2021 21:22:54
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<int> lan[100000];
vector<int> lat[100000];
int n,m;

int pls[100000];
int mns[100000];
// in asta memorez un nod care a fost deja atribuit unei comp conexe
int vist[100000];

void dfs(int nod, vector<int> la[], int vis[])
{
    vis[nod] = 1;
    for (auto& el: la[nod])
    {
        if (!vis[el])
            dfs(el, la, vis);
    }
}

int main()
{
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int n1, n2;
        in >> n1 >> n2;
        lan[n1-1].push_back(n2-1);
        lat[n2-1].push_back(n1-1);
    }

    int nr_total = 0;
    vector<vector<int>> res(100000);
    for (int i = 0; i < n; i++)
    {
        if (vist[i])
            continue;

        dfs(i, lan, pls);
        dfs(i, lat, mns);

        for (int i = 0; i < n; i++)
        {
            if (pls[i] == 1 && mns[i] == 1)
            {
                res[nr_total].push_back(i);
                vist[i] = 1;
            }
        }
        nr_total ++;

        // reset mns and pls
        for (int i = 0; i < n; i++)
        {
            pls[i] = 0;
            mns[i] = 0;
        }
    }

    out << nr_total << '\n';
    for (int i = 0; i < nr_total; i++)
    {
        for (auto& el: res[i])
            out << el+1 << ' ';
        out << '\n';
    }

    return 0;
}