Pagini recente » Cod sursa (job #1449724) | Cod sursa (job #2925421) | Cod sursa (job #2511417) | Cod sursa (job #2503480) | Cod sursa (job #1185794)
#include<fstream>
#include<deque>
#include<vector>
#define N 100100
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,i,x,y,nrctc,viz[N];
vector<int>v[N],vt[N],sol[N];
deque<int>dq;
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);
dq.push_back(x);
}
inline void dfs1(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])
dfs1(*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(!dq.empty())
{
while(!dq.empty() && !viz[dq.back()])
dq.pop_back();
if(dq.empty())
break;
++ nrctc;
dfs1(dq.back());
}
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;
}