Pagini recente » Cod sursa (job #2982838) | Cod sursa (job #2114911) | Cod sursa (job #197760) | Cod sursa (job #357197) | Cod sursa (job #2380373)
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100001], vt[100001];
vector<vector<int>> scc;
bool viz[100001];
int n, m, k;
stack<int> st;
void dfs(int nod)
{
viz[nod] = 1;
for (int i = 0; i < v[nod].size(); i++)
if (!viz[v[nod][i]])
dfs(v[nod][i]);
st.push(nod);
}
void dfst(int nod)
{
viz[nod] = 1;
scc[k].push_back(nod);
for (int i = 0; i < vt[nod].size(); i++)
if (!viz[vt[nod][i]])
dfst(vt[nod][i]);
}
int main()
{
ifstream cin("ctc.in");
ofstream cout("ctc.out");
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
k = 0;
for (int i = 1; i <= n; i++)
viz[i] = 0;
vector<int> vid;
scc.push_back(vid);
while (!st.empty())
{
int temp = st.top();
st.pop();
if (!viz[temp])
{
vector<int> vid;
scc.push_back(vid);
k++;
dfst(temp);
}
}
cout << k << endl;
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < scc[i].size(); j++)
cout << scc[i][j] << ' ';
cout << '\n';
}
return 0;
}