Pagini recente » Cod sursa (job #2672466) | Cod sursa (job #1151676) | Cod sursa (job #167563) | Cod sursa (job #1278756) | Cod sursa (job #945032)
Cod sursa(job #945032)
#include<fstream>
#include<vector>
using namespace std;
vector<int> st, st2, graph[100005], gt[100005];
vector<vector<int> > ctc;
int vis[100005], vis2[100005];
void dfs1(int x){
vis[x] = 1;
st.push_back(x);
for(int i = 0; i < graph[x].size(); ++i)
if(!vis[graph[x][i]])
dfs1(graph[x][i]);
}
void dfs2(int x){
vis2[x] = 1;
st2.push_back(x);
for(int i = 0; i < gt[x].size(); ++i)
if(!vis2[gt[x][i]])
dfs2(gt[x][i]);
}
int main(){
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
in >> n >> m;
for(int i = 1; i <= m; ++i){
int x, y;
in >> x >> y;
graph[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!vis[i])
dfs1(i);
for(int i = n - 1; i >= 0; --i)
if(!vis2[st[i]]){
dfs2(st[i]);
ctc.push_back(st2);
st2.clear();
}
out << ctc.size() << "\n";
for(int i = 0; i < ctc.size(); ++i){
for(int j = 0; j < ctc[i].size(); ++j)
out << ctc[i][j] << " ";
out << "\n";
}
return 0;
}