Cod sursa(job #3341091)

Utilizator bogdan_.f2Fulga Bogdan bogdan_.f2 Data 17 februarie 2026 20:56:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> ctc[100003];
vector <int> L[100003];
vector <int> G[100003];
int st[100003],varf,viz[100003],nrc,n,m;
void DFSF(int k)
{int j;
    //g<<k<<" ";
    viz[k]=1;
    for(j=0;j<L[k].size();j++)
        if(viz[L[k][j]]==0) DFSF(L[k][j]);
    st[++varf]=k;
}
//Acum viz[k]=1 inseamna nevizitat si 0 vizitat
void DFS(int k)
{int j;
    //g<<k<<" ";
    viz[k]=0;
    for(j=0;j<G[k].size();j++)
        if(viz[G[k][j]]==1) DFS(G[k][j]);
    ctc[nrc].push_back(k);
}
void constrCTC()
{
    int i;
    for(i=1;i<=n;i++)
        if(viz[i]==0) DFSF(i);
    for(i=n;i>=1;i--)
        if(viz[st[i]]==1) {nrc++;DFS(st[i]);}
}
int main()
{
    int x,y,i,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        L[x].push_back(y);
        G[y].push_back(x);
    }
    constrCTC();
    g<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
        {
            sort(ctc[i].begin(),ctc[i].end());
            for(j=0;j<ctc[i].size();j++)
                              g<<ctc[i][j]<<" ";
            g<<'\n';
    }
    return 0;
}