Cod sursa(job #2342015)

Utilizator dragos231456Neghina Dragos dragos231456 Data 12 februarie 2019 15:47:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#define N 100005
#define node vecini[x][i]
#define nod tr[x][i]
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> vecini[N],tr[N],comp[N];
int q[N],n,m,x,y,l,seen[N],k;

void dfs(int x)
{
    seen[x]=1;
    for(int i=0;i<vecini[x].size();++i) if(!seen[node]) dfs(node);
    q[++k]=x;
}

void kaju(int x)
{
    seen[x]=1;
    comp[l].push_back(x);
    for(int i=0;i<tr[x].size();++i) if(!seen[nod]) kaju(nod);
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        vecini[x].push_back(y);
        tr[y].push_back(x);
    }
    for(int i=1;i<=n;++i) if(!seen[i]) dfs(i);
    for(int i=1;i<=n;++i) seen[i]=0;
    ++k; while(--k) if(!seen[q[k]])
    {
        ++l;
        kaju(q[k]);
    }
    g<<l<<'\n';
    for(int i=1;i<=l;++i,g<<'\n') for(int j=0;j<comp[i].size();++j) g<<comp[i][j]<<' ';
    return 0;
}