Pagini recente » Cod sursa (job #483407) | Cod sursa (job #1673742) | Cod sursa (job #2000533) | Istoria paginii runda/road_to_ioi_5/clasament | Cod sursa (job #560179)
Cod sursa(job #560179)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define nmax 100010
#define pb push_back
ofstream fout("ctc.out");
vector<int> G[nmax];
vector<int> GT[nmax];
vector<int> comp;
vector<vector<int> > sol;
int N,M;
int viz1[nmax],viz2[nmax];
stack<int> s;
void dfs1(int x)
{
if(viz1[x]) return;
viz1[x]=1;
vector<int>::iterator it;
for(it=G[x].begin();it<G[x].end();it++)
{
dfs1(*it);
}
s.push(x);
}
void dfs2(int x)
{
if(viz2[x]) return;
viz2[x]=1;
comp.pb(x);
vector<int>::iterator it;
for(it=GT[x].begin();it<GT[x].end();it++)
{
dfs2(*it);
}
}
void solve()
{
int i;
for(i=1;i<=N;i++)
{
if(!viz1[i])
{
dfs1(i);
}
}
int u;
while(!s.empty())
{
u=s.top();
s.pop();
// cout<<u<<"\n";
if(!viz2[u])
{ comp.clear();
dfs2(u);
sol.pb(comp);
}
}
fout<<sol.size()<<"\n";
vector<vector<int> >::iterator it;
vector<int>::iterator jt;
for(it=sol.begin();it<sol.end();it++)
{
for(jt=it->begin();jt<it->end();jt++)
{
fout<<*jt<<" ";
}
fout<<"\n";
}
}
void cit()
{
ifstream fin("ctc.in");
int i,x,y;
fin>>N>>M;
for(i=1;i<=M;i++)
{
fin>>x>>y;
G[x].pb(y);
GT[y].pb(x);
}
fin.close();
}
int main()
{
cit();
solve();
fout.close();
return 0;
}