Pagini recente » Cod sursa (job #2221375) | Cod sursa (job #59168) | Cod sursa (job #1617422) | Cod sursa (job #2887417) | Cod sursa (job #1734932)
#include <bitset>
#include <vector>
#include <stack>
#include <stdio.h>
#define N 100010
using namespace std;
vector <int> graf[N];
vector <int> inv_graf[N];
vector <int> solutie[N];
stack <int> coada;
bitset <N> v;
int n , m ;
void read()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 1 ; i <= m ; i++)
{
int a,b;
scanf("%d %d",&a,&b);
graf[a].push_back(b);
inv_graf[b].push_back(a);
}
}
void parcurg(int x)
{
vector <int> :: iterator it;
v[x] = true;
for(it = graf[x].begin(); it != graf[x].end(); ++it)
{
if(!v[*it])
parcurg(*it);
}
coada.push(x);
}
void parcurg_inv(int x , int contor)
{
solutie[contor].push_back(x);
vector <int> :: iterator it;
v[x] = true;
for(it = inv_graf[x].begin(); it != inv_graf[x].end(); ++it)
{
if(!v[*it])
parcurg_inv(*it, contor);
}
}
void afisam(int lim)
{
for(int i = 0 ; i < lim ; i++)
{
for(vector <int> :: iterator it = solutie[i].begin() ; it != solutie[i].end() ; ++it)
printf("%d ",*it);
printf("\n");
}
}
void rezolvare()
{
int numar = 0;
for(int i = 1; i <= n ; i++)
{
if(!v[i])
parcurg(i);
}
v = false;
while(!coada.empty())
{
int x = coada.top();
coada.pop();
if(!v[x])
{
parcurg_inv(x,numar);
numar++;
}
}
printf("%d\n",numar);
afisam(numar);
}
int main()
{
read();
rezolvare();
return 0;
}