Cod sursa(job #1006278)

Utilizator MKLOLDragos Ristache MKLOL Data 6 octombrie 2013 19:53:58
Problema 2SAT Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

#define pb push_back

using namespace std;

vector<int> g[102020],stack;
vector<int> aux;
vector<vector <int> > comp;
int viz[101010];
int low[101010];
int iss[101010];
int k,index=1;
int N,M,x,y;

void printv(vector<int> v){

    for(int i=0;i<v.size();++i){
        printf("%d ",v[i]);
    }
    printf("\n");

}
void show_stack(){
for(int i=1;i<=k;++i){
    printf("%d %d\n",stack[i],low[stack[i]]);

}

}

void df(int x){

    viz[x] = index;
    low[x] = index;
    stack[++k] = x;
    iss[x] = 1;
    ++index;
    for(int i=0;i<g[x].size();++i){
        if(viz[g[x][i]] == 0){
            df(g[x][i]);
            low[x] = min(low[x],low[g[x][i]]);
        }
        else{
            if(iss[g[x][i]]){
                low[x] = min(low[x],low[g[x][i]]);
            }
        }
    }
    if(low[x] == viz[x]){
        //printf("%d %d %d\n",x,low[x],stack[k]);
        aux.clear();

        do{
            aux.pb(stack[k]);
            iss[stack[k]] = 0;
            --k;
        }while(stack[k+1] != x);
        //show_stack();

        comp.pb(aux);
    }



}



int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);

scanf("%d%d",&N,&M);
stack.resize(N+10);
    for(int i=1;i<=M;++i){
        scanf("%d%d",&x,&y);
        g[x].pb(y);
    }
    for(int i=1;i<=N;++i){
        if(viz[i]==0){
            df(i);
        }
    }
    printf("%d\n",comp.size());

    for(int i=0;i<comp.size();++i){
        printv(comp[i]);
    }
    return 0;
}