Pagini recente » Cod sursa (job #1487510) | Cod sursa (job #783188) | Cod sursa (job #211127) | Cod sursa (job #541500) | Cod sursa (job #2159505)
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()
ifstream fi("/home/keloo/Projects/algorithms/ctc.in");
ofstream fo("/home/keloo/Projects/algorithms/ctc.out");
int n,m,x,y,idx[100001],idxc=1,in[100001],low[100001];
vector<int> g[100001],con;
vector<vector<int>> scc;
stack<int> s;
void tarjan(const int n, const vector <int>* adj)
{
idx[n] = low[n] = idxc;
idxc ++;
s.push(n), in[n] = 1;
vector <int>::const_iterator it;
for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
if (!idx[*it])
tarjan(*it, adj),
low[n] = min(low[n], low[*it]);
else if (in[*it])
low[n] = min(low[n], low[*it]);
}
if (idx[n] == low[n]) {
con.clear();
int node;
do {
con.push_back(node = s.top());
s.pop(), in[node] = 0;
}
while (node != n);
scc.push_back(con);
}
}
int main() {
fi >> n >> m;
rep(i,0,m) {
fi >> x >> y;
g[x].push_back(y);
}
rep(i,1,n+1) {
if (!idx[i]) tarjan(i,g);
}
fo << scc.size() << endl;
for (auto x:scc) {
for (auto y:x) fo << y << ' ';
fo << endl;
}
return 0;
}