Pagini recente » Cod sursa (job #260354) | Cod sursa (job #2309191) | Cod sursa (job #250829) | Cod sursa (job #1956706) | Cod sursa (job #1414801)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nr, nrsol;
int postordine[100005];
vector<int> V[100005], W[100005], sol[100005];
bool used[100005];
void dfs(int nod)
{
used[nod] = true;
for (vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
if (!used[*it])
dfs(*it);
postordine[++nr] = nod;
}
void dfsT(int nod)
{
used[nod] = false;
sol[nrsol].push_back(nod);
for (vector<int>::iterator it = W[nod].begin(); it != W[nod].end(); ++it)
if (used[*it])
dfsT(*it);
}
int main()
{
fin >> N >> M;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
W[nod2].push_back(nod1); // graf transpus
}
for (int i = 1; i <= N; ++i)
if (!used[i])
dfs(i);
for (int i = N; i >= 1; --i)
if (used[postordine[i]])
{
++nrsol;
dfsT(postordine[i]);
}
fout << nrsol << '\n';
for (int i = 1; i <= nrsol; ++i)
{
for (vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
fout << *it << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}