Pagini recente » Cod sursa (job #1152688) | Cod sursa (job #1493636) | Cod sursa (job #2041200) | Cod sursa (job #511117) | Cod sursa (job #1902962)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
void dfsa(int x);
void dfsb(int x);
void solve();
void citire();
void afisare();
int N, M, nrc, st[100001], l, t;
bool viza[100001], vizb[100001];
vector<int> muchiia[100001];
vector<int> muchiib[100001];
vector<int> ctc[100001];
int main()
{
citire();
solve();
afisare();
return 0;
}
void citire()
{
fi >> N >> M;
for (int i = 1;i <= M;i++)
{
int x, y;
fi >> x >> y;
muchiia[x].push_back(y);
muchiib[y].push_back(x);
}
return;
}
void solve()
{
for (int i = 1;i <= N;i++)
if (!viza[i])
dfsa(i);
for (int i = N;i >= 1;i--)
{
if (!vizb[st[i]])
{
nrc++;
dfsb(st[i]);
}
}
return;
}
void dfsa(int x)
{
viza[x] = true;
for (int i = 0;i < muchiia[x].size();i++)
if(!viza[muchiia[x][i]])
dfsa(muchiia[x][i]);
st[++l] = x;
return;
}
void dfsb(int x)
{
ctc[nrc].push_back(x);
vizb[x] = true;
for (int i = 0;i < muchiib[x].size();i++)
if (!vizb[muchiib[x][i]])
dfsb(muchiib[x][i]);
return;
}
void afisare()
{
fo << nrc << '\n';
for (int i = 1;i <= nrc;i++)
{
for (int j = 0;j < ctc[i].size();j++)
fo << ctc[i][j] << ' ';
fo << '\n';
}
return;
}