Pagini recente » Cod sursa (job #2931745) | Cod sursa (job #2038847) | Cod sursa (job #236507) | Cod sursa (job #2143119) | Cod sursa (job #2632936)
// Plus-Minus
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100'001;
int n, m, p[NMAX], mn[NMAX], cnt;
vector<int> G[NMAX], GT[NMAX];
vector< vector<int> > sol;
void Read() {
f >> n >> m;
while(m--) {
int x, y;
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void dfs1(int node) {
p[node] = 1;
for(int neighbor : G[node])
if(!p[neighbor])
dfs1(neighbor);
}
void dfs2(int node) {
mn[node] = 1;
for(int neighbor : GT[node])
if(!mn[neighbor])
dfs2(neighbor);
}
void restoreArray(int *v,const int& length,const int& value) {
for(int i = 0;i <= length;++i)
v[i] = value;
}
void PlusMinus() {
vector<int> strong_component(n + 1, -1);
for(int i = 1;i <= n;++i) {
if(strong_component[i] == -1) {
cnt++;
dfs1(i);
dfs2(i);
vector<int> comp;
for (int node = 1; node <= n; ++node) {
if (p[node] && mn[node]) {
strong_component[node] = cnt;
comp.push_back(node);
}
}
sol.push_back(comp);
restoreArray(p, n, 0);
restoreArray(mn, n, 0);
}
}
}
void Print() {
g << cnt << '\n';
for(vector<int> vct : sol) {
for (int it : vct)
g << it << ' ';
g << '\n';
}
}
int main() {
Read();
PlusMinus();
Print();
return 0;
}