Pagini recente » Cod sursa (job #266434) | Cod sursa (job #754575) | Cod sursa (job #516953) | Cod sursa (job #2422416) | Cod sursa (job #1498219)
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <bitset>
#define nmax 100005
using namespace std;
int n,m,a;
vector <int> v[nmax],p[nmax];
vector <int> l[nmax];
stack <int> s;
bitset <nmax> b;
void dfsgraph(int x)
{
b[x]=1;
for (int i=0;i<v[x].size();i++)
if (!b[v[x][i]])
dfsgraph(v[x][i]);
s.push(x);
}
void dfstrans(int x)
{
b[x]=1;
l[a].push_back(x);
for (int i=0;i<p[x].size();i++)
if (!b[p[x][i]])
dfstrans(p[x][i]);
}
void kosaraju()
{
int i,j,x;
for (i=1;i<=n;i++)
if (!b[i])
dfsgraph(i);
b.reset();
while (!s.empty()) {
x=s.top();
s.pop();
if (b[x]==0)
a++,dfstrans(x);
}
printf("%d\n",a);
for (i=1;i<=a;i++) {
sort(l[i].begin(),l[i].end());
for (j=0;j<l[i].size();j++)
printf("%d ",l[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int i,j,x,y;
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) {
scanf("%d %d",&x,&y);
v[x].push_back(y);
p[y].push_back(x);
}
kosaraju();
return 0;
}