Cod sursa(job #2792315)

Utilizator bananamandaoneTudor Cosmin Oanea bananamandaone Data 1 noiembrie 2021 14:07:57
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.18 kb
#include <bits/stdc++.h>

using namespace std;

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


class graf {
private:
    int n, m, k;
    int dist[100003];
    bool orientat = false;
    vector<int> h[100003];
    vector<int> transpus[100003];
    vector<int> ctc[100003];
    bitset<100003> viz;
    queue< pair<int, int> >q;
    stack<int> s;

    void dfs(int nod);

    void dfsctc(int nod);

    void bfs(int s);

public:
    graf()
    {
        n = m = k = 0;
        for(int i = 1; i <= 100000; i++)
            dist[i] = -1;
    }

    void set_graf(int noduri, int muchii, bool Orientat);

    void adauga_muchie(int x, int y);

    void conexe();

    void distante(int s);

    void sortare_topologica();

    void componente_tare_conexe();
};

graf g;

int main()
{
    int n, m, x, y;

    fin >> n >> m;
    g.set_graf(n, m, true);

    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.adauga_muchie(x,y);
    }
    g.componente_tare_conexe();

    fin.close();
    fout.close();
    return 0;
}


void graf :: set_graf(int noduri, int muchii, bool Orientat)
{
    n = noduri;
    m = muchii;
    orientat = Orientat;
}

void graf :: adauga_muchie(int x, int y)
{
    if(orientat)
    {
        h[x].push_back(y);
        transpus[y].push_back(x); // ctc
    }
    else
    {
        h[x].push_back(y);
        h[y].push_back(x);
    }
}

void graf :: dfs(int nod)
{
    viz[nod] = 1;
    for(auto i : h[nod])
        if(!viz[i])
            dfs(i);

    // pentru sortarea topologica si ctc
    s.push(nod);
}

void graf :: dfsctc(int nod)
{
    viz[nod] = 1;
    ctc[k].push_back(nod);
    for(auto i : transpus[nod])
        if(!viz[i])
            dfsctc(i);
}

void graf :: bfs(int s)
{
    pair<int, int> nod;
    q.push({s, 0});
    viz[s] = 1;
    dist[s] = 0;

    while(!q.empty())
    {
        nod = q.front();
        dist[nod.first] = nod.second;
        q.pop();

        for(auto i : h[nod.first])
            if(!viz[i])
            {
                q.push({i, nod.second + 1});
                viz[i] = 1;
            }
    }
}

void graf :: conexe()
{
    int nrc;
    nrc = 0;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
        {
            dfs(i);
            nrc++;
        }
    fout << nrc << "\n";
}

void graf :: distante(int s)
{
    bfs(s);
    for(int i = 1; i <= n; i++)
        fout << dist[i] << " ";
    fout << "\n";
}

void graf :: sortare_topologica()
{
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    while(!s.empty())
    {
        fout << s.top() << " ";
        s.pop();
    }
    fout << "\n";
}

void graf :: componente_tare_conexe()
{
    int top;
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    viz.reset();
    while(!s.empty())
    {
        top = s.top();
        s.pop();
        if(!viz[top])
        {
            k++;
            dfsctc(top);
        }
    }

    fout << k << "\n";
    for(int i = 1; i <= k; i++)
    {
        for(auto j : ctc[i])
            fout << j << " ";
        fout<<"\n";
    }
}