Cod sursa(job #2509458)

Utilizator altcontnoualt cont altcontnou Data 14 decembrie 2019 11:21:42
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int>graf[100005];
vector<int>transpus[100005];
int n, m, from, to;
bool marcata_normal[100005], marcata_transpus[100005];
bool e_componenta[100005];
int ind_rez=1;
vector<int>rez[100005];
void parcurgere_graf(int ind)
{
    marcata_normal[ind]=1;
    for (auto &v:graf[ind])
        if (!marcata_normal[v])
            parcurgere_graf(v);
}

void parcurgere_transpus(int ind)
{
    marcata_transpus[ind]=1;
    for (auto &v:transpus[ind])
        if (!marcata_transpus[v])
            parcurgere_transpus(v);
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i)
    {
        f >> from >> to;
        graf[from].push_back(to);
        transpus[to].push_back(from);
    }
    for (int i=1; i<=n; ++i)
    {
        if (!e_componenta[i])
        {
            parcurgere_graf(i);
            parcurgere_transpus(i);
            for (int j=1; j<=n; ++j)
            {
                if (marcata_normal[j] && marcata_transpus[j])
                {
                    rez[ind_rez].push_back(j);
                    e_componenta[j]=1;
                }
                marcata_normal[j]=0;
                marcata_transpus[j]=0;
            }
            ++ind_rez;
        }
    }
    g << ind_rez-1 << '\n';
    for (int i=1; i<ind_rez; ++i)
    {
        for (auto &v:rez[i])
            g << v << ' ';
        g << '\n';
    }
    return 0;
}