Pagini recente » Cod sursa (job #734986) | Cod sursa (job #923010) | Cod sursa (job #964404) | Cod sursa (job #1648961) | Cod sursa (job #2679816)
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
int i, j, aux, n, m, x, y, k;
bool viz[Nmax], viz2[Nmax];
vector <int> comp[Nmax], g[Nmax], gt[Nmax];
stack <int> S;
void dfs(int x)
{
viz[x] = true;
for(int i = 0; i < g[x].size(); i ++)
{
int aux = g[x][i];
if(viz[aux] == false)dfs(aux);
}
S.push(x);
}
void dfst(int x)
{
viz2[x] = true;
for(int i = 0; i < gt[x].size(); i ++)
{
int aux = gt[x][i];
if(viz2[aux] == false)dfst(aux);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for(i = 1; i <= m; i ++)
{
scanf("%d %d", &x, &y);
g[x].push_back(y);
gt[y].push_back(x); //graful transpus
}
for(i = 1; i <= n; i ++)
if(viz[i] == false)dfs(i);
k = 1;
while(!S.empty())
{
x = S.top();
dfst(x);
while(viz2[x] == true && !S.empty())
{
comp[k].push_back(x);
S.pop();
if(!S.empty())x = S.top();
}
k ++;
}
printf("%d\n", k - 1);
for(i = 1; i < k; i ++)
{
for(j = 0; j < comp[i].size(); j ++)
printf("%d ", comp[i][j]);
printf("%s", "\n");
}
return 0;
}