Pagini recente » Cod sursa (job #331622) | Cod sursa (job #770154) | Cod sursa (job #2622336) | Cod sursa (job #241060) | Cod sursa (job #3145209)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
vector<vector<int>> grph = vector<vector<int>>(100001);
vector<vector<int>> grph2 = vector<vector<int>>(100001);
vector<bool> viz = vector<bool>(100001, false);
queue<int> pri;
int cnt = 0;
vector<vector<int>>ctc = vector<vector<int>>(100001);
void dfs1(int x){
viz[x] = true;
pri.push(x);
for (const auto &item: grph[x]) {
if(!viz[item]){
dfs1(item);
}
}
}
void dfs2(int x){
viz[x] = true;
ctc[cnt].push_back(x);
for (const auto &item: grph2[x]) {
if(viz[item] ==false){
dfs2(item);
}
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
grph[x].push_back(y);
grph2[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfs1(i);
}
}
viz = vector<bool>(100001, false);
while (!pri.empty()) {
int k = pri.front();
if (viz[k] == false) {
cnt++;
dfs2(k);
}
pri.pop();
}
fout<<cnt;
for(int i=1;i<=cnt;i++){
fout<<endl;
for (const auto &item: ctc[i]) {
fout<<item<<" ";
}
}
};