Pagini recente » Cod sursa (job #2197664) | Cod sursa (job #1021573) | Cod sursa (job #892381) | Cod sursa (job #1506609) | Cod sursa (job #2195455)
#include <stdio.h>
#include <deque>
#include <bitset>
#include <cstring>
#include <vector>
using namespace std;
FILE *f,*g;
int start1[100002],start2[100002];///dimensiunea=nr de noduri;
int t1[3][400002],t2[3][400002];///dimensiunea 2*nr de muchii
int succesor[100002],predecesor[100002],tot;
deque <int> q;
bitset <100002> viz1;
bitset <100002> viz2;
vector <int> vecini[100002];
void dfs1(int nod)
{
int no;
viz1[nod]=1;
no=start1[nod];
while(no)
{
if(!viz1[t1[0][no]])
dfs1(t1[0][no]);
no=t1[1][no];
}
q.push_back(nod);
}
void dfs2(int nod)
{
int no;
viz2[nod]=1;
no=start2[nod];
while(no)
{
if(!viz2[t2[0][no]])
dfs2(t2[0][no]);
no=t2[1][no];
}
vecini[tot].push_back(nod);
}
int main()
{
int n,m,i,j,k1=0,o,cont,k2=0;
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
fscanf(f,"%d %d",&n,&m);
for(o=1;o<=m;++o)
{
fscanf(f,"%d %d",&i,&j);
++k1;
t1[0][k1]=j,t1[1][k1]=start1[i],start1[i]=k1;
++k2;
t2[0][k2]=i,t2[1][k2]=start2[j],start2[j]=k2;
}
for(i=1;i<=n;++i)
if(!viz1[i])
dfs1(i);
/*while(!q.empty())
{
x=q.front();
fprintf(g,"%d ",x);
q.pop_front();
}*/
int x;
while(!q.empty())
{
x=q.back();
q.pop_back();
if(!viz2[x])
dfs2(x),++tot;
}
fprintf(g,"%d\n",tot);
for(i=0;i<tot;++i)
{
for(j=0;j<vecini[i].size();++j)
fprintf(g,"%d ",vecini[i][j]);
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}