Cod sursa(job #2980041)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 16 februarie 2023 10:15:07
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <set>
#include <vector>
using namespace std;
#define PB push_back
#define N 100001
ifstream in("ctc.in");
ofstream out("ctc.out");

int n, m,  ctc[N], nrctc, viz[N];
vector<int> la[N], li[N];
set<int> s1, s2;

void citire()
{
    in >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        unsigned int x, y;
        in >> x >> y;
        la[x].PB(y);
        li[y].PB(x);
    }
    in.close();
}

void V_clear()
{
    for(int i = 1; i <= n; ++i)
        viz[i] = 0;
}

void dfs(int x)
{
    viz[x] = 1;
    s1.insert(x);
    for(int i = 0; i < (int)la[x].size(); ++i)
    {
        int y = la[x][i];
        if (!viz[y] && !s1.count(y))
            dfs(y);
    }
    viz[x] = 0;
}

void dfsi(int x)
{
    viz[x] = 1;
    s2.insert(x);
    for(int i = 0; i < (int)li[x].size(); ++i)
    {
        int y = li[x][i];
        if (!viz[y] && !s2.count(y))
            dfsi(y);
    }
    viz[x] = 0;
}

void CTC()
{
    for(int i = 1; i <= n; ++i)
        if(!ctc[i])
        {
            ++nrctc;
            s1.clear();
            s2.clear();
            //V_clear();
            dfs(i);
            //V_clear();
            dfsi(i);
            for(set<int> :: iterator it = s1.begin(); it != s1.end(); ++it)
            {
                int x = *it;
                if(s2.count(x))
                    ctc[x] = nrctc;
            }
        }
}

int main()
{
    citire();
    CTC();
    out << nrctc << '\n';
    for(int i = 1; i <= nrctc; ++i)
    {
        for(int j = 1; j <= n; ++j)
            if(ctc[j] == i)
                out << j << ' ';
        out << '\n';
    }
    return 0;
}