Pagini recente » Cod sursa (job #1686873) | Cod sursa (job #2638879) | Cod sursa (job #330851) | Cod sursa (job #1982145) | Cod sursa (job #2250518)
#include <bits/stdc++.h>
using namespace std;
vector <int> graff[100001];
vector <int> reverseGraff[100001];
vector <int> values(100001);
vector <int> CTC[100001];
int vizitate[100001];
int ctc[100001];
int numberOfCTC = 0;
void dfsGraff(int nod) {
vizitate[nod] = 1;
for (auto x : graff[nod]) {
if (vizitate[x] == 0) {
dfsGraff(x);
}
}
values.push_back(nod);
}
void dfsRevGraff(int nod, int pozitie){
CTC[pozitie].push_back(nod);
vizitate[nod] = 0;
for (auto x : reverseGraff[nod]){
if(vizitate[x]){
dfsRevGraff(x, pozitie);
}
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
f >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
f >> x >> y;
graff[x].push_back(y);
reverseGraff[y].push_back(x);
}
for (int i = 1; i<=n; i++){
if(vizitate[i] == 0) {
dfsGraff(i);
}
}
reverse(values.begin(), values.end());
for (auto x : values){
if (vizitate[x]){
numberOfCTC ++;
dfsRevGraff(x, numberOfCTC);
}
}
g << numberOfCTC << "\n";
for (int i = 1; i <= numberOfCTC; i++){
for( auto j : CTC[i]){
g << j << " ";
}
g << "\n";
}
return 0;
}