Pagini recente » Cod sursa (job #1342944) | Cod sursa (job #1090846) | Cod sursa (job #202842) | Rating Baroana Alexandru-Catalin (Zenhaji) | Cod sursa (job #2071854)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N_MAX = 1e5 + 5;
int N, M, use[N_MAX], v[N_MAX], k, NrConexe = 1;
vector <int> G[N_MAX], T[N_MAX], Com[N_MAX];
void DFS1(int node){
use[node] = 1;
for (int vecin : G[node])
if (!use[vecin]){
use[vecin] = 1;
DFS1(vecin);
}
v[++k] = node;
}
void DFS2(int node){
use[node] = 2;
Com[NrConexe].push_back(node);
for (int vecin : T[node]){
if (use[vecin] == 1){
DFS2(vecin);
}
}
}
int main()
{
in >> N >> M;
for (int i = 1; i <= M; ++i){
int x, y; in >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
if (!use[i]){
DFS1(i);
}
for (int i = k; i >= 1; --i){
if (use[v[i]] == 1){
DFS2(v[i]);
NrConexe++;
}
}
out << NrConexe-1 << '\n';
for (int i = 1; i <= NrConexe; out << '\n', ++i)
for (int ceva : Com[i])
out << ceva << " ";
return 0;
}