Cod sursa(job #2534148)

Utilizator AlbertUngureanuAlbert AlbertUngureanu Data 30 ianuarie 2020 09:56:33
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;

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

int N,M;
int nR;
bool Plus[100005],Minus[100005],V[100005];
vector<int>Ad[100005],AdT[100005],Comp[100005];

void citire()
{
    int x,y;
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>x>>y;
        Ad[x].push_back(y);
        AdT[y].push_back(x);
    }
}

void BFS(int nod)
{
    queue<int>Q;
    int P;
    Plus[nod]=1;
    Q.push(nod);
    while(!Q.empty())
    {
        P=Q.front();
        Q.pop();
        for(unsigned i=0;i<Ad[P].size();i++)
            if(!Plus[Ad[P][i]])
            {
                Plus[Ad[P][i]]=1;
                Q.push(Ad[P][i]);
            }
    }
    Minus[nod]=1;
    Q.push(nod);
    while(!Q.empty())
    {
        P=Q.front();
        Q.pop();
        for(unsigned i=0;i<AdT[P].size();i++)
            if(!Minus[AdT[P][i]])
            {
                Minus[AdT[P][i]]=1;
                Q.push(AdT[P][i]);
            }
    }
    nR++;
    for(int i=1;i<=N;i++)
        if(i!=nod && Plus[i] && Minus[i])
        {
            V[i]=1;
            Comp[nR].push_back(i);
        }
    Comp[nR].push_back(nod);
    V[nR]=1;
}

void rezolvare()
{
    for(int i=1;i<=N;i++)
        if(!V[i])
        {
            BFS(i);
            memset(Minus,0,sizeof(Minus));
            memset(Plus,0,sizeof(Plus));
        }
    fout<<nR<<'\n';
    for(int i=1;i<=nR;i++)
    {
        //sort(Comp[i].begin(),Comp[i].end());
        for(unsigned j=0;j<Comp[i].size();j++)
            fout<<Comp[i][j]<<" ";
        fout<<'\n';
    }
}

int main()
{
    citire();
    rezolvare();
    return 0;
}