Cod sursa(job #2759644)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 19 iunie 2021 15:10:28
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
using namespace std;
FILE*in=fopen("ctc.in","r");
FILE*out=fopen("ctc.out","w");
int n,m,i,x,y,ct;
bool viz[100005];
int comp[100005];
queue<queue<int> > qq;
queue<int> q;
stack<int> s;
queue<int> v[100005],rev[100005];
void dfs(int nod)
{
    viz[nod]=1;
    while(!v[nod].empty())
    {
        if(viz[v[nod].front()]==0)
        {
            dfs(v[nod].front());
        }
        v[nod].pop();
    }
    s.push(nod);
}
void ctcf(int nod)
{
    q.push(nod);
    viz[nod]=1;
    while(!rev[nod].empty())
    {
        if(viz[rev[nod].front()]==0)
        {
            ctcf(rev[nod].front());
        }
        rev[nod].pop();
    }
}
int main()
{
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        v[x].push(y);
        rev[y].push(x);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
        }
    }
    memset(viz,0,sizeof(viz));
    ct=0;
    while(!s.empty())
    {
        ctcf(s.top());
        qq.push(q);
        while(!q.empty())
        {
            q.pop();
        }
        s.pop();
        while(!s.empty()&&viz[s.top()]==1)
        {
            s.pop();
        }
        ct++;
    }
    fprintf(out,"%d\n",ct);
    while(!qq.empty())
    {
        while(!qq.front().empty())
        {
            fprintf(out,"%d ",qq.front().front());
            qq.front().pop();
        }
        fprintf(out,"\n");
        qq.pop();
    }
}