Pagini recente » Cod sursa (job #109790) | Cod sursa (job #2599174) | Borderou de evaluare (job #804571) | Cod sursa (job #2863185) | Cod sursa (job #1260511)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
int nrCTC;
vector <int> G[MAXN], Gt[MAXN], Res[MAXN];
stack <int> S;
bool Used[MAXN];
void DFS(int node)
{
Used[node] = 1;
for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
{
int v = *it;
if (!Used[v])
DFS(v);
}
S.push(node);
}
void DFSt(int node)
{
Res[nrCTC].push_back(node);
Used[node] = 1;
for (vector <int> :: iterator it = Gt[node].begin(); it != Gt[node].end(); ++it)
{
int v = *it;
if (!Used[v])
DFSt(v);
}
}
void Componente_Tare_Conexe()
{
for (int i = 1; i <= N; ++i)
if (!Used[i])
DFS(i);
for (int i = 1; i <= N; ++i)
Used[i] = 0;
while (!S.empty())
{
int node = S.top();
if (!Used[node])
{
++nrCTC;
DFSt(node);
}
S.pop();
}
fout << nrCTC << '\n';
for (int i = 1; i <= nrCTC; ++i)
{
for (int j = 0; j < Res[i].size(); ++j)
fout << Res[i][j] << " ";
fout << '\n';
}
}
int main()
{
fin >> N >> M;
for (int i = 1, a, b; i <= M; ++i)
{
fin >> a >> b;
G[a].push_back(b);
Gt[b].push_back(a);
}
Componente_Tare_Conexe();
fin.close(); fout.close();
return 0;
}