Cod sursa(job #937117)

Utilizator nutipasa16Macovei Claudiu nutipasa16 Data 9 aprilie 2013 20:25:51
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<fstream>
#include<vector>
#include<stack>
#define MAX_N 100
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack<int> s,where;
int n,m,x,y,nr;
void dfs(vector<int>adj[], vector<int> &visited, int node, stack<int> &s)
{
	visited[node]=1;
	for(unsigned int i=0;i<adj[node].size();i++)
		if(visited[adj[node][i]]==0)
			dfs(adj, visited, adj[node][i],s);
	s.push(node);
}
vector<int> from_where;
int main()
{
	f>>n>>m;
	vector<int> adj[n+1],adj_inv[n+1];
	vector<int> visited1(n+1,0), visited2(n+1,0);
	for(int i=1;i<=m;i++)
	{
		f>>x>>y;
		adj[x].push_back(y);
		adj_inv[y].push_back(x);
	}
	dfs(adj, visited1,1,s);
	while(!s.empty())
	{
		x = s.top();
		if(visited2[x]==0)
		{
			nr++;
			from_where.push_back(x);
			dfs(adj_inv, visited2, x, where);
		}
		s.pop();
	}
	g<<nr<<'\n';
	from_where.pop_back();
	while(!from_where.empty())
	{
		while(where.top()!=from_where.back())
		{
			g<<where.top()<<" ";
			where.pop();
		}
		g<<'\n';
		from_where.pop_back();
	}
	while(!where.empty())
	{
		g<<where.top()<<" ";
		where.pop();
	}
	return 0;
}