Pagini recente » Cod sursa (job #2522795) | Cod sursa (job #1959455) | Cod sursa (job #583292) | Cod sursa (job #859510) | Cod sursa (job #2928902)
#include <bits/stdc++.h>
using namespace std;
ostream &operator<<(ostream &out, vector<int> v) {
for (auto x: v) {
out << x << " ";
}
out << "\n";
return out;
}
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, j, tmp1, tmp2, ctc;
vector<vector<int>> graf;
vector<bool> visited;
vector<vector<int>> transpus;
stack<int> tst;
vector<vector<int>> result;
vector<int> partial;
/**
* Sortare topologica
* @param n
*/
inline void topSort(const int &n){
visited[n] = true;
for(const int &vecin : graf[n]){
if(!visited[vecin]){
topSort(vecin);
}
}
tst.push(n);
}
/**
* Parcurgere DFS
* @param n
*/
void dfs(const int &n){
visited[n] = true;
for(const int &vecin : transpus[n]){
if(!visited[vecin]){
dfs(vecin);
}
}
partial.push_back(n);
}
int main() {
fin >> n >> m;
graf.resize(n + 1);
visited.resize(n + 1, false);
transpus.resize(n + 1);
// Construim graful si transpusa sa
for(i = 0; i < m; ++i){
fin >> tmp1 >> tmp2;
graf[tmp1].push_back(tmp2);
transpus[tmp2].push_back(tmp1);
}
// Facem sortare topologica pe graf
for(i = 1; i <= n; ++i){
if(!visited[i])
topSort(i);
}
visited.erase(visited.begin(), visited.end());
visited.resize(n + 1, false);
// Trecem prin stiva sortarii topologice pana ramanem fara elemente
while(!tst.empty()){
tmp1 = tst.top();
tst.pop();
// Daca elementul nu a fost vizitat, pornim un DFS in trasnpusa
if(!visited[tmp1]){
++ctc;
partial.erase(partial.begin(), partial.end());
dfs(tmp1);
result.push_back(partial);
}
}
fout << ctc << '\n';
for(const vector<int> &comp : result)
fout << comp;
return 0;
}