Pagini recente » Cod sursa (job #248813) | Cod sursa (job #1176555) | Cod sursa (job #160052) | Cod sursa (job #1459573) | Cod sursa (job #3336332)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<vector<int>> la;
vector<vector<int>> lat;
vector<vector<int>> ctc;
vector<bool> viz;
stack<int> st;
int c = 0;
void dfs1(int s) {
viz[s] = true;
for(int v : la[s]) {
if(!viz[v]) dfs1(v);
}
st.push(s);
}
void dfs2(int s, vector<int> &compCurr) {
viz[s] = true;
compCurr.push_back(s);
for(int v : lat[s]) {
if(!viz[v]) dfs2(v, compCurr);
}
}
int main() {
int n, m, x, y;
cin >> n >> m;
la.assign(n + 1, {});
lat.assign(n + 1, {});
viz.assign(n + 1, 0);
for(int i = 1; i <= m; i++) {
cin >> x >> y;
la[x].push_back(y);
lat[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!viz[i]) dfs1(i);
viz.assign(n + 1, 0);
while(!st.empty()) {
int curr = st.top();
st.pop();
if(!viz[curr]) {
vector<int> compCurr;
dfs2(curr, compCurr);
ctc.push_back(compCurr);
}
}
cout << ctc.size() << endl;
for(vector<int> vec : ctc) {
for(int x : vec) {
cout << x << ' ';
}
cout << endl;
}
return 0;
}