Cod sursa(job #968982)

Utilizator dropsdrop source drops Data 3 iulie 2013 10:30:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("ctc.in");
ofstream gg("ctc.out");
#define max 100001
vector<int> vv[max], qq;
vector<vector<int> > ll;
bool ww[max], ss[max];
int n, m, cc[max], zz[max], mm[max], k=1, p;
 
void trj(int x){
    int y;
    ww[x]=1;
    zz[x]=k;
    mm[x]=k;
    k++;
    cc[++p]=x;
    ss[x]=1;
    for(int i=0;i<(int)vv[x].size();i++){
        y=vv[x][i];
        if(!ww[y]){
            trj(y);
            mm[x]=min(mm[x], mm[y]);
        } else
        if(ss[y]){
            mm[x]=min(mm[x], zz[y]);
        }
    }
    if(mm[x]==zz[x]){
        qq.clear();
        do{
            y=cc[p--];
            ss[y]=0;
            qq.push_back(y);
        }while(y!=x);
        ll.push_back(qq);
    }
}
 
void sol(){
    for(int i=1;i<=n;i++)
    if(!ww[i]){
        trj(i);
    }
    gg << ll.size() << "\n";
    for(int i=0;i<(int)ll.size();i++){
    for(int j=0;j<(int)ll[i].size();j++) gg << ll[i][j] << " "; gg<<"\n"; }
}
 
int main(){
    int a, b;
    ff >> n >> m;
    for(int i=0;i<m;i++){
        ff >> a >> b;
        vv[a].push_back(b);
    }
    sol();
}