Pagini recente » Cod sursa (job #193932) | Cod sursa (job #915414) | Cod sursa (job #77185) | Cod sursa (job #1774419) | Cod sursa (job #324791)
Cod sursa(job #324791)
#include <vector>
#include <fstream>
using namespace std;
#define nmax 100001
vector<int> a[nmax],at[nmax],sol[nmax];
int viz[nmax],n,m,S[nmax],nr,nrc;
ifstream f("ctc.in");
ofstream g("ctc.out");
void read()
{
f>>n>>m;
int x,y,i;
for(i=1;i<=n;i++)
{
a[i].push_back(0);
at[i].push_back(0);
}
for(i=1;i<=m;i++)
{
f>>x>>y;
a[x][0]++;
a[x].push_back(y);
at[y][0]++;
at[y].push_back(x);
}
}
void dfs(int x)
{
S[++nr]=x;
viz[x]=1;
long i;
for(i=1;i<=a[x][0];i++)
if(!viz[a[x][i]])
dfs(a[x][i]);
}
void dfst(int x)
{
viz[x]=0;
sol[nrc][0]++;
sol[nrc].push_back(x);
for(long i=1;i<=at[x][0];i++)
if(viz[at[x][i]])
dfst(at[x][i]);
}
void solve()
{
long i,j,x;
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
while(nr>0)
{
x=S[nr--];
if(viz[x])
{
nrc++;
sol[nrc].push_back(0);
dfst(x);
}
}
}
void show()
{
g<<nrc<<endl;
long i,j;
for(i=1;i<=nrc;i++)
{
for(j=1;j<=sol[i][0];j++)
g<<sol[i][j]<<" ";
g<<endl;
}
}
int main()
{
read();
solve();
show();
return 0;
}