Cod sursa(job #2759645)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 19 iunie 2021 15:11:21
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 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;
vector<int> v[100005],rev[100005];
void dfs(int nod)
{
    viz[nod]=1;
    for(int t=0;t<v[nod].size();t++)
    {
        if(viz[v[nod][t]]==0)
        {
            dfs(v[nod][t]);
        }
    }
    s.push(nod);
}
void ctcf(int nod)
{
    q.push(nod);
    viz[nod]=1;
    for(int t=0;t<rev[nod].size();t++)
    {
        if(viz[rev[nod][t]]==0)
        {
            ctcf(rev[nod][t]);
        }
    }
}
int main()
{
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        v[x].push_back(y);
        rev[y].push_back(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();
    }
}