Pagini recente » Cod sursa (job #514920) | Cod sursa (job #1282570) | Cod sursa (job #844924) | Cod sursa (job #1417259) | Cod sursa (job #999843)
Cod sursa(job #999843)
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
const int Nmax = 100005;
vector<int> G[ Nmax ],Gt[ Nmax ],answer[ Nmax ];
stack <int> S;
bitset <Nmax> used;
int N,M,ctc;
void read()
{
scanf("%d%d",&N,&M);
int x,y;
for(int i = 1; i <= M; ++i)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void DFS(int nodc)
{
vector<int>::iterator it;
used.set(nodc);
for(it=G[nodc].begin();it!=G[nodc].end();++it)
if(used[*it]==false)
DFS(*it);
S.push(nodc);
}
void DFS_t(int nodc)
{
vector<int>::iterator it;
used.set(nodc);
answer[ctc].push_back(nodc);
for(it=Gt[nodc].begin();it!=Gt[nodc].end();++it)
if(used[*it]==false)
DFS_t(*it);
}
void solve()
{
for(int i = 1; i <= N; ++i)
if(used[i]==false) DFS(i);
used.reset();
while(!S.empty())
{
if(used[ S.top() ] == false)
{
DFS_t(S.top());
++ctc;
}
S.pop();
}
}
void print()
{
printf("%d\n",ctc);
for(int i = 0; i < ctc; ++i)
{
for(vector<int>::iterator it=answer[i].begin();it!=answer[i].end();++it)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
solve();
print();
return 0;
}