Pagini recente » Cod sursa (job #541053) | Cod sursa (job #933575) | Cod sursa (job #2948757) | Cod sursa (job #2282175) | Cod sursa (job #1324928)
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstdlib>
#include<iomanip>
#define maxN 100001
#define maxM 200001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[maxN],Gt[maxN],sol[maxN];
stack<int>st;
int st_sol[maxN];
int n,m,t,nrc;
bool viz[maxN];
void df(int nod)
{
viz[nod]=true;
for(int i=0;i<G[nod].size();i++)
if( viz[G[nod][i]] ==false )
df(G[nod][i]);
st_sol[++t]=nod;
}
void df2(int nod,int comp)
{
viz[nod]=true;
sol[comp].push_back(nod);
for(int i=0;i<Gt[nod].size();i++)
if( viz[Gt[nod][i]]==false )
{
df2(Gt[nod][i],comp);
}
}
void com_tari_conexe()
{
int i,nod;
for(i=n;i>=1;i--)
if(viz[i] == false)
df(i);
fill(viz+1,viz+n+1,false);
for(i=n;i>=1;i--)
{
nod=st_sol[i];
if(!viz[nod])
{
nrc++;
df2(nod,nrc);
}
}
}
void citire()
{
int i,a,b;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>a>>b;
G[a].push_back(b);
Gt[b].push_back(a);
}
}
void afisare()
{
int i,j;
g<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{
for(j=0;j<sol[i].size();j++)
g<<sol[i][j]<<" ";
g<<'\n';
}
}
int main()
{
citire();
com_tari_conexe();
afisare();
return 0;
}