Pagini recente » Cod sursa (job #1186268) | Cod sursa (job #2897850) | preONI 2008 - Sponsori si premii | Cod sursa (job #2550264) | Cod sursa (job #2130593)
#include<bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
vector <int> G[N],GT[N];
int n,m;
inline void read()
{
freopen("ctc.in","rt",stdin);
scanf("%d%d",&n,&m);
// memset(a,0,sizeof(a));
int i,x,y;
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
//a[x][y]=1;
G[x].push_back(y);
GT[y].push_back(x);
}
}
/*void floyd()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(!a[i][j]) a[i][j]=a[i][k]*a[k][j];
}*/
int cn;
queue<int> q;
vector<int> C[N];
int viz[N];
void bfs(int i)
{
int x,j,k,nod;
q.push(i);
viz[++cn]=i;
while(!q.empty())
{
x=q.front();
q.pop();
C[cn].push_back(x);
//if(!viz[x])
for(j=1;j<=n;j++)
//if(a[x][j] && a[j][x] && !viz[j] && j!=x)
{//C[cn].push_back(j);
viz[j]=cn;
q.push(j);
}
}
}
void solve()
{
int i,j;
for(int i=1;i<=n;i++)
{for(int j=1;j<=n;j++)
// cout<<a[i][j]<<' ';
cout<<endl;
}
for(int i=1;i<=n;++i)
if(!viz[i])
{
bfs(i);
//viz[i]=1;
}
// cout<<cn;
for(i=1;i<=cn;i++)
{for(j=0;j<C[i].size();j++)
cout<<C[i][j]<<' ';
cout<<endl;
}
}
stack<int> s;
vector<int> sol[N];
int nc;
void dfs(int nod)
{
int i;
s.push(nod);
q.push(nod);
//cout<<nod<<' ';
viz[nod]=1;
for(i=0;i<G[nod].size();i++)
if(!viz[G[nod][i]])
dfs(G[nod][i]);
}
void dft(int nod)
{
viz[nod]=0;
sol[nc].push_back(nod);
for(int i=0;i<GT[nod].size();i++)
if(viz[GT[nod][i]])
dft(GT[nod][i]);
}
int main()
{
int i,j,x;
read();
//floyd();
freopen("ctc.out","wt",stdout);
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
while(!q.empty())
{
x=q.front();
q.pop();
if(viz[x]==1)
{
++nc;
dft(x);
//cout<<'\n';
}
}
cout<<nc<<'\n';
for(i=1;i<=nc;i++)
{
for(j=0;j<sol[i].size();j++)
cout<<sol[i][j]<<' ';
cout<<'\n';
}
}