Pagini recente » Cod sursa (job #1108205) | Cod sursa (job #1792377) | Cod sursa (job #1107824) | Cod sursa (job #2582860) | Cod sursa (job #1397533)
#include<fstream>
#include<stack>
#include<vector>
#define N 100100
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int x,n,y,nrctc,m,i,viz[N];
vector<int>v[N],vt[N],sol[N];
stack<int>st;
inline void dfs(int x){
viz[x] = 1;
for(vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
if(!viz[*it])
dfs(*it);
st.push(x);
}
inline void dfst(int x){
viz[x] = 0;
sol[nrctc].push_back(x);
for(vector<int>::iterator it = vt[x].begin(); it != vt[x].end(); ++it)
if(viz[*it])
dfst(*it);
}
int main()
{
f >> n >> m;
for(i = 1; i <= m; ++i)
{
f >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
for(i = 1; i <= n; ++i)
if(!viz[i])
dfs(i);
while(!st.empty())
{
while(!st.empty() && !viz[st.top()])
st.pop();
if(st.empty())
break;
++nrctc;
dfst(st.top());
st.pop();
}
g << nrctc << '\n';
for(i = 1; i <= nrctc; ++i, g << '\n')
for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
g << *it << ' ';
return 0;
}