Cod sursa(job #968821)

Utilizator dropsdrop source drops Data 2 iulie 2013 20:28:58
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 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], tt[max], qq;
vector<vector<int> > ll;
bool ww[max], aa[max], bb[max];
int n, m;

void dfs(int x, vector<int> *vv, bool *aa){
	aa[x]=1;
	for(int i=0;i<(int)vv[x].size();i++)
	if(!ww[vv[x][i]] && !aa[vv[x][i]]) dfs(vv[x][i], vv, aa);
}

void sol(){
	for(int i=1;i<=n;i++)
	if(!ww[i]){
		memset(aa, 0, sizeof(aa));
		memset(bb, 0, sizeof(bb));
		dfs(i, vv, aa);
		dfs(i, tt, bb);
		qq.clear();
		for(int i=1;i<=n;i++)
		if(aa[i] && bb[i]){ qq.push_back(i); ww[i]=1; }
		ll.push_back(qq);
	}
	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);
		tt[b].push_back(a);
	}
	sol();
}