Cod sursa(job #2398461)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 5 aprilie 2019 15:52:16
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;

FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");

int n,m;
vector<int> G1[Nmax],G2[Nmax];
int vizitat[Nmax],vizitat2[Nmax];
vector<vector<int>> ans;
stack<int> q;
vector<int> aux;
void dfs1(int x)
{
    q.push(x);
    vizitat[x] = 1;
    for(int i=0;i<(int)G1[x].size();i++)
        if(!vizitat[G1[x][i]])
            dfs1(G1[x][i]);
}

void dfs2(int x)
{
    aux.push_back(x);
    vizitat2[x] =1;
    for(int i=0;i<(int)G2[x].size();i++)
        if(!vizitat2[G2[x][i]])
            dfs2(G2[x][i]);
}

int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
        G1[x].push_back(y);
        G2[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!vizitat[i])
            dfs1(i);
    while(!q.empty())
    {
        int x=q.top();
        q.pop();
        if(!vizitat2[x])
            {
                dfs2(x);
                ans.push_back(aux);
                aux.clear();
            }
    }
    fprintf(g,"%d",ans.size());
    fprintf(g,"\n");
    for(int i=0;i<(int)ans.size();i++)
    {
        for(int j=0;j<(int)ans[i].size();j++)
            fprintf(g,"%d ",ans[i][j]);
        fprintf(g,"\n");
    }
    return 0;
}