Pagini recente » Cod sursa (job #2334707) | Cod sursa (job #1140761) | Cod sursa (job #2513066) | Cod sursa (job #2487681) | Cod sursa (job #2119697)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define in vector<int> :: iterator
#define lim 200005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, trans[lim], nrc, t;
vector<int> G[lim], tG[lim], scc[lim];
bitset<lim> B;
inline void Dfs(int node)
{
B[node] = 1;
for(in it = G[node].begin(); it != G[node].end(); ++it)
if(!B[*it])
Dfs(*it);
trans[++t] = node;
}
inline void Dfs_t(int node)
{
B[node] = 0;
scc[nrc].push_back(node);
for(in it = tG[node].begin(); it != tG[node].end(); ++it)
if(B[*it])
Dfs_t(*it);
}
int main()
{
f >> n >> m;
for(int i = 1; i <= m; ++i)
{
int x, y;
f >> x >> y;
G[x].push_back(y);
tG[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!B[i])
Dfs(i);
for(int i = n; i >= 1; --i)
if(B[trans[i]])
{
++nrc;
Dfs_t(trans[i]);
}
g << nrc << "\n";
for(int i = 1; i <= nrc; ++i)
{
for(in it = scc[i].begin(); it != scc[i].end(); ++it)
g << *it << " ";
g << "\n";
}
}