Mai intai trebuie sa te autentifici.
Cod sursa(job #1519592)
Utilizator | Data | 7 noiembrie 2015 16:04:58 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.54 kb |
#include <iostream>
#include <stack>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
int n, m, nrc;
vector<VI> G1, G2, C;
vector<bool> s;
stack<int> st;
void Read();
void Df1(int x);
void Df2(int x);
int main()
{
Read();
for ( int i = 1; i <= n; i++ )
if ( !s[i] )
Df1(i);
s.assign(n+1, 0);
int x;
while (!st.empty())
{
x = st.top();
st.pop();
if ( !s[x] )
{
nrc++;
Df2(x);
}
//fout << x << ' ' << nrc << '\n';
}
fout << nrc << '\n';
for ( int i = 1; i <= nrc; i++ )
{
for ( const int& y : C[i] )
fout << y << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
G1 = vector<VI>(n+1);
G2 = vector<VI>(n+1);
C = vector<VI>(n+1);
s = vector<bool>(n+1);
int x, y;
while (fin >> x >> y)
{
G1[x].push_back(y);
G2[y].push_back(x);
}
}
void Df1(int x)
{
s[x] = 1;
for ( const int& y : G1[x] )
{
if ( s[y] != 1 )
{
// fout << x << ' ' << y << '\n';
Df1(y);
}
}
st.push(x);
}
void Df2(int x)
{
s[x] = 1;
C[nrc].push_back(x);
for ( const int& y : G2[x] )
{
if ( s[y] != 1 )
{
Df2(y);
}
}
}