Pagini recente » Cod sursa (job #855785) | Cod sursa (job #1591790) | Cod sursa (job #2202761) | Cod sursa (job #2660544) | Cod sursa (job #2891105)
#include <fstream>
#include <vector>
#include <stack>
#pragma GCC optimize("Ofast")
#define nmax 100000
using namespace std;
int f[nmax + 1], nr;
vector<int> ad[nmax + 1], adrev[nmax + 1], ctc[nmax + 1];
stack<int> s;
void dfs1 (int nod)
{
for (auto urm : ad[nod])
if (f[urm] == 0)
f[urm] = 1, dfs1 (urm);
s.push (nod);
}
void dfs2 (int nod)
{
ctc[nr].push_back (nod);
for (auto urm : adrev[nod])
if (f[urm] == 0)
f[urm] = 1, dfs2 (urm);
}
int main()
{
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
int n, m, i, a, b;
ios_base::sync_with_stdio (0), cin.tie (0), cout.tie (0);
cin >> n >> m;
for (i = 1; i <= m; i++)
cin >> a >> b, ad[a].push_back (b), adrev[b].push_back (a);
for (i = 1; i <= n; i++)
if (f[i] == 0)
f[i] = 1, dfs1 (i);
for (i = 1; i <= n; i++)
f[i] = 0;
while (!s.empty())
{
if (f[s.top()] == 0)
f[s.top()] = 1, ++nr, dfs2 (s.top());
s.pop();
}
cout << nr << '\n';
for (i = 1; i <= nr; i++)
{
for (auto a : ctc[i])
cout << a << ' ';
cout << '\n';
}
return 0;
}