Pagini recente » Cod sursa (job #1034790) | Cod sursa (job #297006) | Cod sursa (job #1114780) | Cod sursa (job #1928664) | Cod sursa (job #3278840)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 2e5 + 1;
vector<int> v[N], rev_v[N], componente(N);
stack<int> S;
int p[N], m[N];
void dfs(int nod)
{
p[nod] = 1;
for (int i = 0; i < v[nod].size(); i++)
{
if (p[v[nod][i]] == 0)
{
dfs(v[nod][i]);
}
}
}
void dfs_minus(int nod)
{
m[nod] = 1;
for (int i = 0; i < rev_v[nod].size(); i++)
{
if (m[rev_v[nod][i]] == 0)
{
dfs_minus(rev_v[nod][i]);
}
}
}
signed main()
{
int n, M,nr_componente=0;
in >> n >> M;
for (int i = 1, a, b; i <= M; i++)
{
in >> a >> b;
v[a].push_back(b);
rev_v[b].push_back(a);
}
for(int i = 1 ; i <= n ; ++i)
if(componente[i] == 0)
{
for(int j = 1; j <= n ; ++j)
m[j] = p[j] = 0;
nr_componente ++;
dfs(i);
dfs_minus(i);
for(int j = 1; j <= n ; ++j)
if(m[j] == 1 && p[j] == 1)
componente[j] = nr_componente;
}
out << nr_componente << '\n';
for (int i = 1; i <= nr_componente; i++)
{
for (int j = 1; j <= n; j++)
{
if (componente[j] == i)
out << j << ' ';
}
out << '\n';
}
}