Cod sursa(job #2299786)

Utilizator Victor_InczeVictor Incze Victor_Incze Data 10 decembrie 2018 08:38:44
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define MAXN 100005

using namespace std;

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

int n, m, nrc, x, y;
bitset <MAXN> s, p, ctc;
vector <int> g[MAXN], nug[MAXN], sol[MAXN];

void df1(int x)
{
	s[x]=1;
	for (int i=0; i<g[x].size(); i++)
        if(!s[g[x][i]])
			df1(g[x][i]);
}

void df2(int x)
{
	p[x]=1;
	for (int i=0; i<nug[x].size(); i++)
		if(!p[nug[x][i]])
			df2(nug[x][i]);
}

int main()
{
    in >> n >> m;
    for (int i=1; i<=m; i++)
    {
    	in >> x >> y;
    	g[x].push_back(y);
    	nug[y].push_back(x);
    }
	for (int i=1; i<=n; i++)
		if(!ctc[i])
		{
			//memset(s,0,MAXN);
			//memset(p,0,MAXN);
			for (int j=1; j<=n; j++)
                s[j]=p[j]=0;
			nrc++;
			df1(i);
			df2(i);
			for (int j=1; j<=n; j++)
				if (s[j] && p[j])
					ctc[j]=1, sol[nrc].push_back(j);
		}
	out << nrc << '\n';
	for (int i=1; i<=nrc; i++)
	{
		for (int j=0; j<sol[i].size(); j++)
				out << sol[i][j] << " ";
		out << '\n';
	}
    return 0;
}