Cod sursa(job #2405972)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 15 aprilie 2019 11:36:17
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
//---------------------------------------------------------------------------
//Variabile globale
int n,rez[100001],nr;
vector<int>v[100001],v2[100001],rasp[100001];
//---------------------------------------------------------------------------
//Functii
void citeste();
void rezolva();
//---------------------------------------------------------------------------
int main()
{
    citeste();
    rezolva();
    return 0;
}
//---------------------------------------------------------------------------
void bfs(int nod)
{
    queue<int>q;
    q.push(nod);
    rez[nod]=-nod;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = 0;i < v[x].size();++i)
        {
            if(rez[v[x][i]] != nod && rez[v[x][i]] >= 0)
            {
                rez[v[x][i]] = nod;
                q.push(v[x][i]);
            }
        }
    }
    q.push(nod);
    rasp[nr].push_back(nod);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = 0;i < v2[x].size();++i)
        {
            if(rez[v2[x][i]] == nod)
            {
                rez[v2[x][i]] = -nod;
                rasp[nr].push_back(v2[x][i]);
                q.push(v2[x][i]);
            }
        }
    }
}
//---------------------------------------------------------------------------
void rezolva()
{
    for(int i = 1;i <= n;++i)
        if(rez[i] >= 0)
        {
            nr++;
            bfs(i);
        }
    g << nr <<'\n';
    for(int i = 1;i <= nr;++i)
    {
        for(int j = 0;j < rasp[i].size();++j)
            g << rasp[i][j] << " ";
        g << '\n';
    }
}
//---------------------------------------------------------------------------
void citeste()
{
    int m;
    f >> n >> m;
    while(m--)
    {
        int a,b;
        f >> a >> b;
        v[a].push_back(b);
        v2[b].push_back(a);
    }
}