Cod sursa(job #2369531)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 6 martie 2019 00:22:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int VAL=100005;

int N, M, i, j, A, B, nod;
int K, comp[VAL], st[VAL], top;
bool viz[VAL];
vector <int> G[VAL], Ginv[VAL], SOL[VAL];

void DFS(int nod)
{
    vector <int> :: iterator it;
    viz[nod]=true;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        if (viz[*it]==true)
            continue;
        DFS(*it);
    }
    st[++top]=nod;
}

void Assign_To_Comp(int nod)
{
    vector <int> :: iterator it;
    comp[nod]=K;
    SOL[K].push_back(nod);
    for (it=Ginv[nod].begin(); it!=Ginv[nod].end(); it++)
    {
        if (comp[*it]!=0)
            continue;
        Assign_To_Comp(*it);
    }
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B;
        G[A].push_back(B);
        Ginv[B].push_back(A);
    }
    for (i=1; i<=N; i++)
        if (viz[i]==false)
            DFS(i);
    while (top>0)
    {
        nod=st[top];
        top--;
        if (comp[nod]==0)
        {
            K++;
            Assign_To_Comp(nod);
        }
    }
    fout << K << '\n';
    for (i=1; i<=K; i++)
    {
        for (j=0; j<SOL[i].size(); j++)
            fout << SOL[i][j] << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}