Pagini recente » Cod sursa (job #2587457) | Cod sursa (job #579509) | Cod sursa (job #2975458) | Cod sursa (job #2845113) | Cod sursa (job #3268095)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
const int Max = 1e5 + 1;
int n, m, c;
vector<int> g[Max], t[Max], ctc[Max];
bitset<Max> v;
stack<int> s;
void dfs(int node)
{
v[node] = 1;
for(int i: g[node])
if(!v[i])
dfs(i);
s.push(node);
}
void dfs2(int node)
{
ctc[c].push_back(node);
v[node] = 1;
for(int i: t[node])
if(!v[i])
dfs2(i);
}
void kosaraju()
{
for(int i = 1; i <= n; ++i)
if(!v[i])
dfs(i);
v.reset();
while(!s.empty())
{
if(!v[s.top()])
{
++c;
dfs2(s.top());
}
s.pop();
}
}
int main()
{
ios::sync_with_stdio(false);
fin.tie(NULL);
fin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
g[x].push_back(y);
t[y].push_back(x);
}
kosaraju();
fout << c << "\n";
for(int i = 1; i <= c; ++i, fout << "\n")
for(int j: ctc[i])
fout << j << " ";
fin.close();
fout.close();
return 0;
}