Pagini recente » Cod sursa (job #268774) | Cod sursa (job #1854676) | Cod sursa (job #877772) | Cod sursa (job #2803843) | Cod sursa (job #324784)
Cod sursa(job #324784)
#include <vector>
#include <fstream>
using namespace std;
#define nmax 100001
vector<int> a[nmax],at[nmax],sol[nmax];
int viz[nmax],n,m,p[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)
{
viz[x]=1;
p[++nr]=x;
for(int 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(int i=1;i<=at[x][0];i++)
if(viz[at[x][i]])
dfst(at[x][i]);
}
void show()
{
g<<nrc<<endl;
int i,j;
for(i=1;i<=nrc;i++)
{
for(j=1;j<=sol[i][0];j++)
{
g<<sol[i][j]<<" ";
}
g<<endl;
}
}
int main()
{
int i;
read();
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
for(i=1;i<=n;i++)
{
if(viz[p[i]])
{
nrc++;
sol[nrc].push_back(0);
dfst(p[i]);
}
}
show();
return 0;
}