Cod sursa(job #3240804)

Utilizator PetrudpPetru Paun Petrudp Data 20 august 2024 22:50:03
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int N = 25002;

vector<int> graf[N];
vector<int> graft[N];

bool viz1[N], viz2[N];
int n, m, nrc = 0, ctc[N];

void Init()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        graf[x].push_back(y);
        graft[y].push_back(x);
    }
}

void Dfs1(int x)
{
    viz1[x] = true;
    for(auto y : graf[x])
    {
        if(!viz1[y])
        {
            Dfs1(y);
        }
    }
}

void Dfs2(int x)
{
    viz2[x] = true;
    for(auto y : graft[x])
    {
        if(!viz2[y])
        {
            Dfs2(y);
        }
    }
}

int main()
{
    Init();
    for(int i = 1; i <= n; i++)
    {
        if(!ctc[i])
        {
            memset(viz1, false, n + 1);
            memset(viz2, false, n + 1);
            nrc++;
            Dfs1(i);
            Dfs2(i);
            for(int k = 1; k <= n; k++)
            {
                if(viz1[k] && viz2[k])
                {
                    ctc[k] = nrc;
                }
            }
        }
    }
    out << nrc << "\n";
    for(int i = 1; i <= nrc; i++)
    {
        for(int k = 1; k <= n; k++)
        {
            if(ctc[k] == i)
            {
                out << k << " ";
            }
        }
        out << "\n";
    }


    return 0;
}