Pagini recente » Cod sursa (job #442923) | Cod sursa (job #2365377) | Cod sursa (job #2364203) | Cod sursa (job #3030888) | Cod sursa (job #304118)
Cod sursa(job #304118)
#include <algorithm>
#include <stdio.h>
#include <vector>
#define MAX 100010
#define pb push_back
using namespace std;
int n, m;
vector <int> stackCtc;
vector <int> listDrum[MAX], listDrumTr[MAX];
vector <vector <int> > compBic;
vector <int> vctComp;
int enq[MAX];
void dfs(int nod)
{
if (enq[nod])
return;
enq[nod] = 1;
for (int i = 0; i < listDrum[nod].size(); i++)
dfs(listDrum[nod][i]);
stackCtc.pb(nod);
}
void dfsConstr(int nod)
{
if (!enq[nod])
return;
enq[nod] = 0;
for (int i = 0; i < listDrumTr[nod].size(); i++)
dfsConstr(listDrumTr[nod][i]);
vctComp.pb(nod);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (; m; m--)
{
int nod1, nod2;
scanf("%d %d", &nod1, &nod2);
listDrum[nod1].pb(nod2);
listDrumTr[nod2].pb(nod1);
}
// Dfs 1
for (int i = 1; i <= n; i++)
dfs(i);
// Dfs 2
for (; !stackCtc.empty(); stackCtc.pop_back())
{
dfsConstr(stackCtc[stackCtc.size() - 1]);
if (!vctComp.empty())
compBic.pb(vctComp);
vctComp.clear();
}
printf("%d\n", compBic.size());
for (int i = 0; i < compBic.size(); i++)
{
for (int j = 0; j < compBic[i].size(); j++)
printf("%d ", compBic[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}