Pagini recente » Cod sursa (job #2274722) | Cod sursa (job #2153194) | Cod sursa (job #2713220) | Cod sursa (job #458126) | Cod sursa (job #2429865)
#include <stack>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX = 100005;
int nodes, edges;
vector <int> graph[NMAX], revgraph[NMAX], currscc;
vector <vector <int> > scc;
stack <int> st;
bitset <NMAX> seen;
void dfs1(int node)
{
seen[node] = 1;
for (auto i : graph[node])
{
if (seen[i] == 1)
continue;
dfs1(i);
}
st.push(node);
}
void dfs2(int node)
{
seen[node] = 1;
for (auto i : revgraph[node])
{
if (seen[i] == 1)
continue;
dfs2(i);
}
currscc.push_back(node);
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> nodes >> edges;
for (int i = 1;i <= edges;++i)
{
int x, y;
fin >> x >> y;
graph[x].push_back(y);
revgraph[y].push_back(x);
}
for (int i = 1;i <= nodes;++i)
if (seen[i] == 0)
dfs1(i);
seen.reset();
while (!st.empty())
{
while (!st.empty() && seen[st.top()] == 1)
st.pop();
if (st.empty())
break;
currscc.clear();
dfs2(st.top());
scc.push_back(currscc);
st.pop();
}
fout << scc.size() << "\n";
for (int i = 0;i < scc.size();++i, fout << "\n")
for (int j = 0;j < scc[i].size();++j, fout << " ")
fout << scc[i][j];
fin.close();
fout.close();
return 0;
}