Cod sursa(job #752657)

Utilizator zeeboBuzatu Vlad zeebo Data 29 mai 2012 10:02:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream G("ctc.out");
bool sel[200010];
int stiva[200010],m,n,i,nc,nr,x,y;
vector<int> g[200010],gt[200010];
void dfs (int x)
{
int i;
  sel[x]=true;
  for(i=0;i<g[x].size();++i)
    if (!sel[g[x][i]]) dfs(g[x][i]);
  stiva[++nr]=x;
}
void dfts (int x, bool k)
{
   int i;
  sel[x]=true;
  if (k) G<<x<<' ';
  for(i=0; i<gt[x].size();i++)
    if (!sel[gt[x][i]]) dfts(gt[x][i], k);
}
int main ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		g[x].pb(y);
		gt[y].pb(x);
	}
	nc=nr=0;
nr=0; nc=0;
for (i=1;i<=200010;i++) sel[i]=false;
for(i=1;i<=n;i++)
        if (!sel[i]) dfs(i);
for (i=1;i<=200010;i++) sel[i]=false;
    for(i=n;i>0;i--)
        if (!sel[stiva[i]])
        {
            dfts(stiva[i], false);
            nc++;
        }
G<<nc<<'\n';
for (i=1;i<=200010;i++) sel[i]=false;
    for(i=n;i>0;i--)
        if (!sel[stiva[i]])
        {
            dfts(stiva[i], true);
            G<<'\n';
        }
    return 0;
}