Cod sursa(job #2421115)

Utilizator PushkinPetolea Cosmin Pushkin Data 14 mai 2019 12:24:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<unsigned int>> G, Gt, CTC;
vector<bool> pls, mns, viz;
unsigned int n;
void rd()
{
    unsigned int x, y;
    f>>n>>x;
    G.resize(n+1);
    Gt.resize(n+1);
    viz.resize(n+1);
    pls.resize(n+1);
    mns.resize(n+1);
    while(f>>x>>y)
    {
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}
void DFS(unsigned int x)
{
    pls[x]=1;
    for(auto a:G[x])
        if(!pls[a])
            DFS(a);
}
void DFSt(unsigned int x)
{
    mns[x]=1;
    for(auto a:Gt[x])
        if(!mns[a])
            DFSt(a);
}
void Consent_Is_Optional()
{
    unsigned int x=1;
    while(x)
    {
        vector<unsigned int> r;
        DFS(x);
        DFSt(x);
        for(unsigned int i=1;i<=n;i++)
        {
            if(pls[i]&&mns[i])
            {
                r.push_back(i);
                viz[i]=1;
            }
            pls[i]=mns[i]=0;
        }
        CTC.push_back(r);
        x=0;
        for(unsigned int i=1;i<=n;i++)
            if(!viz[i])
        {
            x=i;
            break;
        }
    }
}
int main()
{
    rd();
    Consent_Is_Optional();
    g<<CTC.size();
    for(auto c:CTC)
    {
        for(auto a:c)
            g<<a<<' ';
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}