Pagini recente » Cod sursa (job #1772563) | Cod sursa (job #1489463) | Cod sursa (job #2630514) | Cod sursa (job #1330580) | Cod sursa (job #1283249)
#include <fstream>
#include <list>
#include <stack>
#define DIM 100001
using namespace std;
list <int> nod[DIM],inv[DIM],sol[DIM];
stack <int> st;
bool v[DIM],w[DIM];
int n,m,x,y,cr;
void DFS(int k)
{
v[k]=1;
for(list<int>::iterator i=nod[k].begin();i!=nod[k].end();++i)
{
if(!v[*i])
DFS(*i);
}
st.push(k);
}
void DFST(int k)
{
w[k]=1;
sol[cr].push_back(k);
for(list<int>::iterator i=inv[k].begin();i!=inv[k].end();++i)
{
if(!w[*i])
DFST(*i);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(int i=1;i<=m;++i)
{
f>>x>>y;
nod[x].push_back(y);
inv[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(!v[i]) DFS(i);
while(!st.empty())
{
int vf=st.top();
if(!w[vf])
{
++cr;
DFST(vf);
}
st.pop();
}
g<<cr<<'\n';
for(int i=1;i<=cr;++i)
{
for(list<int>::iterator j=sol[i].begin();j!=sol[i].end();++j)
g<<*j<<" ";
g<<'\n';
}
f.close();
g.close();
return 0;
}