Cod sursa(job #1888257)

Utilizator alex.jilavu17alex jilavu alex.jilavu17 Data 21 februarie 2017 23:38:52
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define NMax 10000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,nr;
vector <int>G[NMax],T[NMax],sol[NMax];
bool mark[NMax];
stack <int>Stack;
void read(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
        T[y].push_back(x);}
}
void dfs1(int nod){
    mark[nod]=true;
    for(vector <int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
        if(mark[*it]==false)
            dfs1(*it);
    Stack.push(nod);}
void dfs2(int nod){
    sol[nr].push_back(nod);
    mark[nod]=true;
    for(vector <int>::iterator it=T[nod].begin();it!=T[nod].end();it++)
        if(mark[*it]==false)
            dfs2(*it);
}
void write(){
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++){
        for(vector <int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
            fout<<*it<<" ";
        fout<<'\n';}
}

int main(){
    read();
    for(int i=1;i<=n;i++)
        if(mark[i]==false)
            dfs1(i);
    memset(mark,false,sizeof(mark));
    while(!Stack.empty()){
        if(mark[Stack.top()]==false){
            nr++;
            dfs2(Stack.top());
        }
        Stack.pop();}
    write();
}