Cod sursa(job #1731016)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 18 iulie 2016 01:28:55
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 100005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int viz[NMAX], low[NMAX],nrviz,inStack[NMAX];
stack<int> st;
vector<vector<int> > res;
vector<int> v[NMAX];

void tarjan(int x) {
	int i,y;

	st.push(x);
	inStack[x]=1;
	viz[x]=low[x]=++nrviz;
	for(i=0;i<v[x].size();++i) {
		y=v[x][i];

		if(!viz[y]) tarjan(y);
		low[x]=min(low[x],low[y]);
	}

	if(viz[x] == low[x]) {
		int p;
		vector<int> v;

		do {
			p=st.top();
			inStack[p]=0;
			st.pop();
			v.pb(p);
		} while(p!=x);
		res.pb(v);
	}
}

int main() {
    int n,i,j,m,x,y;

    fin>>n>>m;
    for(i=0;i<m;++i) {
		fin>>x>>y;
		v[x].pb(y);
    }

    for(i=1;i<=n;++i)
		if(!viz[i]) tarjan(i);

	fout<<res.size()<<'\n';
	for(i=0;i<res.size();++i) {
		for(j=0;j<res[i].size();++j) fout<<res[i][j]<<' ';
		fout<<'\n';
	}

    return 0;
}