Pagini recente » Cod sursa (job #3130314) | Cod sursa (job #768764) | Cod sursa (job #553674) | Cod sursa (job #1064468) | Cod sursa (job #2102891)
#include <cstdio>
#include <vector>
using namespace std;
vector <int>::iterator it;
vector <int> comp[100001],vecin[100001],wecin[100001];
int n,m,i,j,c,mns[100001],pls[100001];
bool v[100001];
void dfs_pls(int k)
{
int i;
pls[k]=c;
for(i=0;i<vecin[k].size();i++)
if(pls[vecin[k][i]]!=c)
dfs_pls(vecin[k][i]);
}
void dfs_mns(int k)
{
int i;
mns[k]=c;
for(i=0;i<wecin[k].size();i++)
if(mns[wecin[k][i]]!=c)
{
if(pls[wecin[k][i]]==c)
{
comp[c].push_back(wecin[k][i]);
v[wecin[k][i]]=1;
}
dfs_mns(wecin[k][i]);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d\n",&n,&m);
while(m)
{
scanf("%d %d\n",&i,&j);
if(i!=j)
{
vecin[i].push_back(j);
wecin[j].push_back(i);
}
m--;
}
for(i=1;i<=n;i++)
if((!mns[i]) || (!pls[i]) || !v[i])
{
c++;
comp[c].push_back(i);
v[i]=1;
dfs_pls(i);
dfs_mns(i);
}
printf("%d\n",c);
for(i=1;i<=c;i++,printf("\n"))
for(it=comp[i].begin();it!=comp[i].end();it++)
printf("%d ",*it);
return 0;
}