Pagini recente » Cod sursa (job #2988399) | Cod sursa (job #2063425) | Cod sursa (job #3236027) | Cod sursa (job #310799) | Cod sursa (job #3032323)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>> l(100001);
vector<vector<int>> lt(100001);
int n,m;
vector<vector<int>> comp;
queue<int> q={};
int visited[100001] ={0};
void dfs1(int x) {
if (visited[x] == 0) {
visited[x] = 1;
for (const auto &item: l[x]) {
if (visited[item] == 0) {
dfs1(item);
}
}
q.push(x);
}
}
void dfs2(int x,vector<int>&c) {
if (visited[x] == 0) {
c.push_back(x);
visited[x] = 1;
for (const auto &item: l[x]) {
if (visited[item] == 0) {
dfs2(item,c);
}
}
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
l[x].push_back(y);
lt[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
dfs1(i);
}
memset(visited, 0, 100000);
int cnt = 0;
while (!q.empty()) {
int k = q.front();
q.pop();
if (visited[k] == 0) {
cnt += 1;
vector<int> cc;
dfs2(k, cc);
comp.push_back(cc);
}
}
fout<<cnt;
for (const auto &item: comp) {
fout<<endl;
for (const auto &item1: item) {
fout<<item1<<" ";
}
}
}