Pagini recente » Cod sursa (job #2942382) | Cod sursa (job #2015404) | Cod sursa (job #163324) | Cod sursa (job #200449) | Cod sursa (job #2062849)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, x, y, time, nr;
vector<int>l[100002],t[100002], color(100002),sol[100002];
stack<pair<int,int> >st;
void dfs(int k){
color[k] = 1;
for(vector<int>::const_iterator it = l[k].begin(); it != l[k].end(); it++){
x = *it;
if(color[x] == 0) dfs(x);
}
color[k] = 2; time = time + 1;
st.push(make_pair(k,time));
}
void dfst(int k){
color[k] = 1;
sol[nr].push_back(k);
for(vector<int>::const_iterator it = t[k].begin(); it != t[k].end(); it++){
if(color[*it] == 0) dfst(*it);
}
color[k] = 2;
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++){
in >> x >> y;
l[x].push_back(y);t[y].push_back(x);
}
for(int i = 1; i <= n; i++){
if(color[i] == 0) dfs(i);
}
for(int i = 1; i <= n; i++) color[i] = 0;
while(!st.empty()){
x = st.top().first; y = st.top().second;
st.pop();
//cout << x << ": " << y << "\n";
if(color[x] == 0) {
nr = nr + 1; dfst(x);
}
}
out << nr << "\n";
for(int i = 1; i <= nr; i++){
for(vector<int>::const_iterator it = sol[i].begin(); it != sol[i].end(); it++) out << *it << " ";
out << "\n";
}
return 0;
}