Pagini recente » Cod sursa (job #2405965) | Cod sursa (job #1197615) | Cod sursa (job #678842) | Cod sursa (job #335120) | Cod sursa (job #1023014)
// componente tare conexe
#include<cstdio>
#include<vector>
#include<cstring>
#define N_MAX 100010
#define M_MAX 200010
#define pb push_back
using namespace std;
vector <int> G[N_MAX];
vector <int> Gt[N_MAX];
bool sel[N_MAX];
int St[N_MAX];
int N,i,NR_SOL,p;
//DF pe graful transpus
inline void DF_Trans(int x,bool ok)
{
vector <int> :: iterator it;
if (ok) printf("%d ",x);
sel[x]=true;
for (it=Gt[x].begin();it!=Gt[x].end();++it)
if (!sel[*it]) DF_Trans(*it, ok);
}
// DF pe graful original
inline void DF(int x)
{
vector <int> :: iterator it;
sel[x]=true;
for (it=G[x].begin();it!=G[x].end();++it)
if (!sel[*it]) DF(*it);
St[++p]=x;
}
inline void Read_Data()
{
int M,i,x,y;
scanf("%d%d",&N,&M);
for (i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
G[x].pb(y);
Gt[y].pb(x);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
Read_Data();
for (i=1;i<=N;i++)
sel[i]=false;
p=0;
for (i=1;i<=N;i++)
if (!sel[i]) DF(i);
// determinarea numarului de componente
NR_SOL=0;
for (i=1;i<=N;i++)
sel[i]=false;
for (i=N;i>0;--i)
if (!sel[St[i]])
{
DF_Trans(St[i],false);
NR_SOL++;
}
printf("%d\n",NR_SOL);
//afisarea componentelor
for (i=1;i<=N;i++)
sel[i]=false;
for (i=N;i>0;--i)
if (!sel[St[i]])
{
DF_Trans(St[i],true);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}