Cod sursa(job #1726704)

Utilizator vancea.catalincatalin vancea.catalin Data 8 iulie 2016 19:07:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DX 100100
using namespace std;
fstream fin("ctc.in",ios::in),fout("ctc.out",ios::out);
typedef vector<int> TI;
TI v1[DX],v2[DX],v,c;
vector<TI> cc;
stack<int> st;
int n,m,ap[DX];
void citire();
void dfs(int nod);
void dfsb(int nod);
int main()
{
    int a,b,i,j;
    citire();
    for(i=1;i<=n;i++) dfs(i);//bagam in stiva
    while(st.empty()==0)
    {
        a=st.top();st.pop();
        if(ap[a]!=0)
        {
            c.clear();
            dfsb(a);
            cc.push_back(c);
        }
    }
    fout<<cc.size()<<"\n";
    for(auto x:cc)
    {
        for(auto y:x) fout<<y<<" ";
        fout<<"\n";
    }
}
void citire()
{
    int a,b,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        v1[a].push_back(b);
        v2[b].push_back(a);
    }
}
void dfs(int nod)
{
    if(ap[nod]!=0) return ;
    ap[nod]=1;
    for(auto x :v1[nod]) dfs(x);
    st.push(nod);
}
void dfsb(int nod)
{
    if(ap[nod]==0) return ;
    ap[nod]=0;
    c.push_back(nod);
    for(auto x :v2[nod]) dfsb(x);
}