Pagini recente » Cod sursa (job #159550) | Cod sursa (job #2640564) | Rating suranyi eduard (Edi16) | Cod sursa (job #582646) | Cod sursa (job #2205529)
#include <fstream>
#include <vector>
#include <algorithm>
const int MAX_V = 100000;
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int V, E;
vector<int> neighbours[MAX_V + 1];
vector<int> neighboursT[MAX_V + 1];
vector<int> L;
vector<int> vertices[MAX_V + 1];
bool visited[MAX_V + 1];
int ctcCount;
void dfs(int u) {
visited[u] = true;
for (int v : neighbours[u])
if (!visited[v])
dfs(v);
L.push_back(u);
}
void dfsT(int u) {
visited[u] = true;
for (int v : neighboursT[u])
if (!visited[v])
dfsT(v);
vertices[ctcCount].push_back(u);
}
int main() {
fin >> V >> E;
for (int i = 0; i < E; i++) {
int u, v;
fin >> u >> v;
neighbours[u].push_back(v);
neighboursT[v].push_back(u);
}
for (int u = 1; u <= V; u++)
if (!visited[u])
dfs(u);
reverse(L.begin(), L.end());
for (int u : L)
visited[u] = false;
for (int u : L)
if (!visited[u]) {
ctcCount++;
dfsT(u);
}
fout << ctcCount << '\n';
for (int i = 1; i <= ctcCount; i++) {
for (int u : vertices[i])
fout << u << ' ';
fout << '\n';
}
return 0;
}