Pagini recente » Cod sursa (job #3122440) | Cod sursa (job #2866914) | Cod sursa (job #1653060) | Cod sursa (job #1938554) | Cod sursa (job #2929068)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
const int N = 1e5 + 1;
vector <int> L[N], T[N];
vector <vector <int> > ctc;
bitset <N> vis;
int n, nr_ctc = -1;
stack<int> st;
void Read()
{
ifstream fin ("ctc.in");
int m;
fin >> n >> m;
while (m--)
{
int x, y;
fin >> x >> y;
L[x].push_back(y);
T[y].push_back(x);
}
fin.close();
}
void First_DFS(int node)
{
vis[node] = 1;
for (auto& next : L[node])
if (!vis[next])
First_DFS(next);
st.push(node);
}
void Second_DFS(int node)
{
vis[node] = 1;
ctc[nr_ctc].push_back(node);
for (auto& next : T[node])
if (!vis[next])
Second_DFS(next);
}
void Kosaraju() {
for (int i = 1; i <= n; i++)
if (!vis[i])
First_DFS(i);
vis.reset();
while (!st.empty())
{
int curr = st.top();
st.pop();
if (!vis[curr])
{
nr_ctc++;
ctc.push_back({});
Second_DFS(curr);
}
}
ofstream fout ("ctc.out");
fout << ctc.size() << "\n";
for (int i = 0; i < ctc.size(); i++, fout << "\n")
for (int j = 0; j < ctc[i].size(); j++)
fout << ctc[i][j] << " ";
fout.close();
}
int main() {
Read();
Kosaraju();
return 0;
}