Pagini recente » Cod sursa (job #2751754) | Cod sursa (job #2428128) | Cod sursa (job #2108958) | Cod sursa (job #1860698) | Cod sursa (job #1904645)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
/*
8 12
1 2
2 6
6 7
7 6
3 1
3 4
2 3
4 5
5 4
6 5
5 8
8 7
*/
int n, m, nr;
vector <vector <int> > a;
vector <vector <int> > arev;
vector <vector <int> > afis;
vector <bool> viz;
stack <int> st;
void df(int k) {
viz[k] = true;
for (int i = 0 ; i < a[k].size(); i++) {
if (viz[a[k][i]] == false) {
df(a[k][i]);
}
}
st.push(k);
}
void dfrev(int k) {
viz[k] = true;
afis[nr].push_back(k);
for (int i = 0 ; i < arev[k].size(); i++) {
if (viz[arev[k][i]] == false) {
dfrev(arev[k][i]);
}
}
}
int main()
{
fin>>n>>m;
a.resize(n + 1);
arev.resize(n + 1);
viz.resize(n + 1);
int x, y;
for (int i = 1; i <= m; i++) {
fin>>x>>y;
a[x].push_back(y);
arev[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (viz[i] == false) {
df(i);
}
}
for(int i = 0; i < viz.size(); i++) {
viz[i] = false;
}
while(!st.empty()) {
int k = st.top();
st.pop();
if(viz[k] == false) {
nr++;
afis.resize(nr + 1);
dfrev(k);
}
}
fout<<nr;
fout<<'\n';
for (int i = 1; i < afis.size(); i++) {
for (int j = 0; j < afis[i].size(); j++) {
fout<<afis[i][j]<<' ';
}
fout<<'\n';
}
/*
cout<<st.size();
while(!st.empty()) {
cout<<st.top()<<' ';
st.pop();
}
*/
fin.close();
fout.close();
return 0;
}
/*
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector <vector <int> > a;
vector <int> st;
vector <bool> viz;
void df(int k) {
viz[k] = true;
for (int i = 0 ; i < a[k].size(); i++) {
if (viz[a[k][i]] == false) {
viz[a[k][i]] = true;
df(a[k][i]);
}
}
st.push_back(k);
}
int main()
{
fin>>n>>m;
a.resize(n + 1);
viz.resize(n + 1);
int x, y;
for (int i = 1; i <= m; i++) {
fin>>x>>y;
a[x].push_back(y);
}
df(2);
for(int i = 0; i < st.size(); i++) {
fout<<st[i]<<' ';
}
fin.close();
fout.close();
return 0;
}
*/