Pagini recente » Cod sursa (job #1370752) | Cod sursa (job #2266246) | Cod sursa (job #2535906) | Cod sursa (job #2070736) | Cod sursa (job #2097012)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DN 100010
using namespace std;
fstream fin("ctc.in", ios::in), fout("ctc.out", ios::out);
vector<int> v1[DN], v2[DN], r[DN];
stack<int> st;
int n,m,ap[DN],nrc=0;
void dfs1(int n);
void dfs2(int n);
int main()
{
int i,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
v1[x].push_back(y);
v2[y].push_back(x);
}
for(i=1;i<=n;i++)
if(ap[i]==0)
dfs1(i);
for(i=1;i<=n;i++) ap[i]=0;
while( st.empty() == 0 )
{
i=st.top(); st.pop();
if(ap[i]==0)
{
nrc++;
dfs2(i);
}
}
fout<<nrc<<"\n";
for(i=1;i<=nrc;i++)
{
for( auto x:r[i]) fout<<x<<" ";
fout<<"\n";
}
}
void dfs1(int n)
{
st.push(n);
ap[n]=1;
for( auto x:v1[n])
{
if(ap[x]==0) dfs1(x);
}
}
void dfs2(int n)
{
ap[n]=1;
r[nrc].push_back(n);
for( auto x:v2[n])
{
if(ap[x]==0)
{
dfs2(x);
}
}
}